← DSA Atlas
Dedicated problem page · #857

Minimum Cost to Hire K Workers

HardHeap and Priority QueueSort by ratio, sliding max-heap of qualitiesGreedy with a bounded max-heap
Solve on LeetCode ↗
857
HardHeap and Priority QueueGreedy with a bounded max-heapSort by ratio, sliding max-heap of qualities

Minimum Cost to Hire K Workers

You want to hire exactly k workers from n candidates, each with a quality[i] and a minimum wage expectation wage[i]. Every hired worker must be paid in proportion to their quality relative to the others in the group, and at least their own minimum wage. Return the minimum total cost to form such a group. Answers within 1e-5 of the true value are accepted.

Open official problem prompt ↗
In plain English

Choose exactly k workers and a single pay-rate that satisfies everyone's minimum wage, minimizing the total payout.

Picture it like this

Setting one hourly rate for a whole crew: the rate is dictated by the most 'expensive' member (highest pay demand per unit of work). To keep the bill down, once that rate is fixed you want teammates who contribute the least billable hours.

Example
Input
quality = [10, 20, 5], wage = [70, 50, 30], k = 2
Output
105.0
Why
Hiring workers 0 and 2 at rate 7 per quality unit (worker 0 needs 70/10 = 7) costs 7*(10+5) = 105, the cheapest valid pair.
Constraints
n == quality.length == wage.length1 <= k <= n <= 10^41 <= quality[i], wage[i] <= 10^4
Pattern lesson

See the pattern, then code

Sort by ratio, sliding max-heap of qualities
Recognition clue

Pay is proportional to quality and floored by each worker's minimum wage, so the whole group's rate is fixed by one worker's wage/quality ratio. Fixing the rate-setter and minimizing summed quality of the rest is a sort-plus-heap greedy.

↗
Heap and Priority Queue

Top k, kth value, repeated minimum extraction, scheduling, or merging sorted streams.. If the paying rate is r (dollars per unit quality), total cost is r * (sum of group qualities). The rate must be at least every member's wage/quality, so it equals the maximum ratio in the group. Sort workers by ratio; when worker i is the highest ratio, pick the k-1 previously seen workers with the smallest qualities to minimize the sum.

New words, made simpleKnow these before the algorithm
Wage-to-quality ratio
wage[i] / quality[i]: the minimum dollars per unit quality worker i will accept.
Rate-setter
The group member with the highest ratio, which forces the rate paid to everyone.
Max-heap of qualities
A heap that lets us evict the largest chosen quality so the running sum stays minimal.
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
Try every k-subset

Combinatorial explosion; impossible for n up to 10^4.

Enumerate all groups of size k, compute each cost, take the min.

Time O(C(n,k) * k)Space O(k)
Best choiceSort by ratio + max-heap

Considers only n rate-setters, each in log time.

Sort by ratio so each worker in turn is the rate-setter, and keep the k smallest qualities seen so far via a max-heap.

Time O(n log n)Space O(n)
The rule we keep true

Invariant

When worker i (in ratio-sorted order) is processed and the heap holds k qualities, those are the k smallest qualities among workers with ratio <= worker i's ratio, so ratio_i * total_quality is the cheapest group whose rate-setter is worker i.

Why this is correct

Reasoning

Any valid group's rate equals its maximum ratio. Fixing that maximum to be worker i means every other member has ratio <= i's, i.e. comes earlier in the sorted order, so it is legal to pay them at rate_i. Given the rate is fixed, cost is proportional to total quality, so choosing the k smallest qualities among eligible workers (heap eviction of the largest) minimizes it. Scanning every i as the rate-setter and taking the minimum covers all optimal groups.

The algorithm in three movesSay these aloud before coding
1Compute each worker's ratio wage/quality and sort ascending by ratio

sorted by ratio: 2.5(q20), 6(q5), 7(q10)

2Iterate; maintain a max-heap of chosen qualities and their running sum

at r=6: sum=25 -> 6*25 = 150

3After adding a worker, if more than k qualities are held, pop the largest to shrink the sum

at r=7: drop q20 -> sum=15 -> 7*15 = 105

4When exactly k are held, the current worker's ratio is the group max; update the answer with ratio * qualitySum

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
r=2.5,q=200
r=6,q=51
r=7,q=102
1 · Readquality=[10,20,5], wage=[70,50,30]
2 · AskRatios ascending?
3 · Update state[(2.5,20),(6,5),(7,10)]
4 · Resultprocess in this order
Key takeaway

Workers sorted by wage/quality ratio; the running set keeps the k smallest qualities under the current rate.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 5Sort by ratio

    Ordering workers by wage/quality lets each worker serve as the rate-setter for all workers before it.

  2. 2
    Lines 10-12Accumulate qualities

    Push each quality (negated for a max-heap) and add it to a running quality sum.

  3. 3
    Lines 13-14Keep only k smallest

    If more than k qualities are held, pop the largest and subtract it, minimizing the sum under the current rate.

  4. 4
    Lines 15-16Score this rate-setter

    Once exactly k qualities are held, the current ratio is the group max; ratio * total_quality is a candidate answer.

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • k == 1 (each worker alone costs exactly their own wage)
  • k == n (only one possible group)
  • workers sharing an identical ratio
  • large qualities that must be evicted once a costlier rate-setter appears
!

Common beginner mistakes

  • Sorting by wage or quality alone instead of the wage/quality ratio
  • Using a min-heap and keeping the largest qualities, inflating the sum
  • Forgetting the answer is a float and using integer arithmetic
  • Recording a cost before the heap actually reaches size k
Check your understanding

Why does the pay-rate for a group equal the maximum wage/quality ratio among its members?

More in Heap and Priority Queue

#215Kth Largest Element in an ArrayBounded min-heap of size k#295Find Median from Data StreamTwo balanced heaps#373Find K Pairs with Smallest Sumsk-way merge with a heap#502IPOGreedy with a max-heap of affordable options#621Task SchedulerFill idle slots around the most frequent task#692Top K Frequent WordsCount then heap-order by frequency and word