Learn
Practice
Interview
Resources
Newsletter
F
Toggle theme
0
F
0
Toggle menu
Animations
← Back to All Animations
Minimum Cost to Hire K Workers
Bookmark
Input
Example 1
Example 2
Equal workers
Small k=2
Custom
quality
=
[10, 20, 5]
,
wage
=
[70, 50, 30]
,
k
=
2
workers
q / wage
10
$70
7.00
20
$50
2.50
5
$30
6.00
0
1
2
workers
q / wage
10
$70
7.00
20
$50
2.50
5
$30
6.00
0
1
2
workers
q / wage
20
$50
2.50
5
$30
6.00
10
$70
7.00
0
1
2
sort by
wage / quality ↑
— the captain's rate prices the team
minCost =
∞
Σ quality =
0
workers
q / wage
20
$50
2.50
5
$30
6.00
10
$70
7.00
0
1
2
heap = [], Σq =
0
, minCost =
∞
minCost =
∞
Σ quality =
20
workers
q / wage
20
$50
2.50
5
$30
6.00
10
$70
7.00
0
1
2
team
k = 2
20
Σq =
20
i
rate
2.50
joins with q
20
→ Σq =
20
(team 1/2)
minCost =
∞
Σ quality =
25
workers
q / wage
20
$50
2.50
5
$30
6.00
10
$70
7.00
0
1
2
team
k = 2
5
20
Σq =
25
i
rate
6.00
joins with q
5
→ Σq =
25
(team 2/2)
minCost =
150.00
Σ quality =
25
workers
q / wage
20
$50
2.50
5
$30
6.00
10
$70
7.00
0
1
2
team
k = 2
5
20
Σq =
25
i
cost = rate
6.00
× Σq
25
=
150.00
→ new minimum!
minCost =
150.00
Σ quality =
35
workers
q / wage
20
$50
2.50
5
$30
6.00
10
$70
7.00
0
1
2
team
k = 2
5
10
20
Σq =
35
i
rate
7.00
joins with q
10
→ Σq =
35
(team 3/2)
minCost =
150.00
Σ quality =
15
workers
q / wage
20
$50
2.50
5
$30
6.00
10
$70
7.00
0
1
2
team
k = 2
5
10
20
Σq =
15
i
team > 2 → evict largest q
20
→ Σq =
15
minCost =
105.00
Σ quality =
15
workers
q / wage
20
$50
2.50
5
$30
6.00
10
$70
7.00
0
1
2
team
k = 2
5
10
Σq =
15
i
cost = rate
7.00
× Σq
15
=
105.00
→ new minimum!
minCost =
105.00
Σ quality =
15
workers
q / wage
20
$50
2.50
5
$30
6.00
10
$70
7.00
rate
0
1
2
team
k = 2
5
10
Σq =
15
Minimum cost =
105.00
algo
master
.
io
Step:
Start: Hire exactly 2 workers as cheaply as possible
0 / 9
Input
Example 1
Example 2
Equal workers
Small k=2
Custom
quality
=
[10, 20, 5]
,
wage
=
[70, 50, 30]
,
k
=
2
0 / 9
algo
master
.
io
Step:
Start: Hire exactly 2 workers as cheaply as possible
