Minimum Cost to Hire K Workers
Minimum Cost to Hire K Workers: hire exactly k workers paid in proportion to their quality, where every worker must earn at least their minimum wage. Return the least total cost.
- n == quality.length == wage.length
- 1 <= k <= n <= 10⁴
- 1 <= quality[i], wage[i] <= 10⁴
- Answers within 10⁻⁵ of the actual answer are accepted
Intuition
Within a paid group everyone shares one wage-per-quality ratio, and that ratio must satisfy the greediest member — so it is the maximum ratio in the group. Sorting workers by ratio means that fixing a worker as the group's most expensive lets every cheaper-ratio worker be a candidate, and the cost is then that ratio times the total quality. Minimising cost therefore means minimising total quality among the k cheapest-quality candidates, which a max-heap maintains as the ratio rises.
When a cost factorises into one value set by the group's extreme member and another that is a sum over the group, sort by the extreme and use a heap for the sum. The pattern — sort to fix one dimension, heap to optimise the other — also drives IPO and Maximum Performance of a Team.
Approach
Before reading on: derive the single rate that satisfies every worker in a group, and write the total cost as a product of two factors. Then work out why sorting by ratio lets you fix one factor and optimise the other independently.
Deriving the payment rule
The two conditions — pay in proportion to quality, and pay each worker at least their minimum wage — combine into a single number per group. If the group is paid at rate R per unit of quality, worker i receives R × quality[i], and this must be at least wage[i], so R >= wage[i] / quality[i]. To satisfy every member at once, R must be the maximum of those ratios. The total cost is then R × Σ quality, which is the product of exactly two quantities — and that factorisation is what makes the problem tractable.
Sorting by ratio to fix one factor at a time
Sort workers by wage / quality ascending and sweep. When worker i is processed, treat their ratio as the group's rate R; every worker seen so far has a ratio no larger, so any of them may join without raising R. This turns a two-variable optimisation into a sequence of one-variable ones: with R pinned by the current worker, the only remaining freedom is which k workers to take, and the cost depends on them solely through their total quality.
A max-heap to keep total quality minimal
Maintain a max-heap of the qualities of the chosen candidates along with their running sum. Push each worker's quality; once the heap holds more than k, pop the largest, since dropping the highest quality reduces the sum by the most. When the heap holds exactly k, the group is the k smallest-quality workers among those with ratio at most the current one, and the candidate cost is ratio × sum. Take the minimum across the sweep. Sorting costs O(n log n) and each worker enters and leaves the heap once, so the total remains O(n log n) with O(k) space.
Solution & live demo
Common pitfalls
Picking the k smallest qualities outright
sort by quality, take the k smallest
sort by ratio, then heap the qualities
Total cost is ratio times total quality, and a low-quality worker can carry a very high ratio that inflates the rate for everyone. Optimising one factor alone ignores the product.
Using a min-heap for the qualities
heapq.heappush(heap, q) heapq.heappop(heap)
heapq.heappush(heap, -q) heapq.heappop(heap)
Evicting must remove the largest quality to keep the sum minimal. A min-heap pops the smallest, discarding the cheapest worker and driving the total up instead of down.
Computing cost before the group is full
best = min(best, ratio * total_quality)
if len(heap) == k:
best = min(best, ratio * total_quality)With fewer than k workers the sum is smaller and produces a cost that no legal hire can achieve, so the reported minimum is below the true answer.
Edge cases
Everyone is hired, and the rate is the largest ratio overall.
The answer is simply the smallest wage, since each worker alone costs their own minimum.
Either may set the rate; the heap still selects the smaller qualities.
They are popped from the heap as soon as the group exceeds k.
Answers within 10⁻⁵ are accepted, so doubles are sufficient.