Module 6 · Advanced Heap

Minimum Cost to Hire K Workers

HardProblem 14 of 14 11 min read ~36 min to solve LeetCode

HeapPriority QueueGreedySortingMath

Asked atGoogleAmazonMicrosoftMetaUber

Problem Statement

You are given arrays quality and wage, where worker i has quality quality[i] and must be paid at least wage[i]. To hire exactly k workers, every hired worker must be paid in proportion to quality using the same rate, and each worker must receive at least their minimum wage. Return the minimum total cost to hire exactly k workers.

Input

Integer arrays quality and wage, plus an integer k for the exact number of workers to hire.

Output

A floating-point number: the minimum possible total wage cost for a valid group of exactly k workers.

Constraints

•1 <= k <= quality.length <= 10^4
•quality.length == wage.length
•1 <= quality[i], wage[i] <= 10^4
•Answers within 10^-5 of the actual answer are accepted

Examples

Example 1

Input:

quality = [10,20,5], wage = [70,50,30], k = 2

Output: 105.00000

Explanation: Hire workers with qualities 10 and 5 at rate 7. They are paid 70 and 35, satisfying both minimum wages for total cost 105.

Example 2

Input:

quality = [3,1,10,10,1], wage = [4,8,2,2,7], k = 3

Output: 30.66667

Explanation: The best group uses a shared wage-to-quality rate of 23 / 3, producing the minimum valid total for three selected qualities.

Learning Objectives

Derive the wage-to-quality ratio insight that turns a group into one limiting worker and a quality sum.
Sort workers by ratio so the current worker can be treated as the highest required rate in the group.
Maintain the k smallest qualities among eligible workers with a max-heap.
Explain why popping the largest quality minimizes cost under a fixed current ratio.

Intuition

Pattern recognition starts when every selected worker must share the same pay rate per quality. For any chosen group, the rate must be at least the largest wage / quality ratio among its workers. Once that rate is fixed, total cost is simply rate * sum of selected qualities.

Sort workers by ratio in ascending order. When the sweep is at a worker with ratio r, all previously seen workers have ratio at most r, so any group formed from them and the current worker can legally be paid at rate r. Under that fixed rate, minimizing cost means minimizing the sum of qualities.

The greedy invariant is: after processing a ratio prefix, the heap and running sum represent the k smallest qualities among workers seen so far whenever at least k workers are available. A max-heap is used because if more than k qualities are present, the largest quality is the one to discard. That keeps the sum as small as possible for the current and future ratio checks.

Common mistakes

×Sorting by wage alone or quality alone instead of by the wage-to-quality ratio.
×Using a min-heap of qualities, which removes the cheapest worker and leaves a larger quality sum.
×Computing a candidate cost before the heap contains exactly **k** workers.
×Forgetting that the current ratio is a double value and should not be truncated with integer division.

Algorithm Explanation

Key idea

For a selected group, the worker with the highest wage / quality ratio determines the minimum shared pay rate. Sort workers by this ratio. As each worker becomes the current highest-ratio worker, choose the k smallest qualities among all workers seen so far and evaluate current ratio * quality sum.

The exchange argument is about the quality sum under a fixed rate. If a candidate group of k workers under the current ratio includes a larger quality a while an eligible smaller quality b is excluded, swapping a out for b keeps every worker eligible under the same ratio and reduces or preserves total cost. Therefore, the best group for the current ratio is exactly the k smallest qualities among the ratio prefix. The max-heap enforces that by ejecting the largest quality whenever the heap grows beyond k.

Heap walkthrough

For quality = [10,20,5], wage = [70,50,30], and k = 2, the ratios in ascending order are quality 20 at ratio 2.5, quality 5 at ratio 6.0, and quality 10 at ratio 7.0. Add quality 20 first; the max-heap is [20] and the quality sum is 20, so no cost is valid yet. Add quality 5; the heap is [20,5], the sum is 25, and the candidate cost is 6.0 * 25 = 150. Add quality 10; the heap is [20,5,10], sum is 35, then pop the largest quality 20, leaving [10,5] and sum 15. At ratio 7.0, the candidate cost is 7.0 * 15 = 105, which is the best.

Algorithm

Pair every worker's quality with wage and sort workers by wage / quality in ascending order using double comparison.
Maintain a max-heap of selected qualities and a running qualitySum.
Sweep workers in ratio order.
Add the current quality to the heap and to qualitySum.
If the heap size exceeds k, poll the largest quality and subtract it from qualitySum.
If the heap size is exactly k, compute current ratio * qualitySum and minimize the answer.
Return the best cost.

Solutions

Solution: Ratio sweep with max-heap of qualities

When to prefer this:

Use this when a group cost is controlled by a maximum ratio or threshold, and the remaining objective under that threshold is to minimize a size-k sum.

Sort workers by their minimum acceptable wage-to-quality ratio. During the sweep, the current worker supplies the highest ratio for any group ending at that point. A max-heap keeps the selected qualities as small as possible by removing the largest quality whenever more than k candidates are present.

Step-by-step

Store each worker as [quality, wage].
Sort workers by wage / quality using double comparison.
Keep largestQualities as a max-heap and qualitySum as the sum of heap entries.
For each worker in ratio order, add their quality to both the heap and the sum.
If the heap size exceeds k, remove the largest quality and subtract it from the sum.
When the heap size is exactly k, compute the current ratio times qualitySum and update the answer.
Return the minimum candidate cost found.

Time

O(n log n)

Space

O(k)

Sorting costs O(n log n), and the heap stores at most k + 1 qualities during the sweep.

Java implementation

Loading…

Dry Run

Sample input

quality = [10,20,5], wage = [70,50,30], k = 2. Workers sorted by ratio are [quality 20, ratio 2.5], [quality 5, ratio 6.0], [quality 10, ratio 7.0].

worker by ratio	ratio	action on max-heap qualities	quality sum	candidate cost	best cost
quality 20, wage 50	2.5	push 20 -> [20]	20	not enough workers	none
quality 5, wage 30	6.0	push 5 -> [20,5]	25	150	150
quality 10, wage 70	7.0	push 10 -> [20,5,10], pop 20 -> [10,5]	15	105	105

At ratio 7.0, the heap has the two smallest qualities among all eligible workers: 10 and 5. Their quality sum is 15, so the best cost is 105.

Interview Tips

Lead with the ratio insight before mentioning the heap. The interviewer needs to hear that any hired group is paid at a shared rate, and the largest wage-to-quality ratio in the group determines that rate. After sorting by ratio, the max-heap has one job: keep the k smallest qualities so the cost under the current rate is minimized.

Likely follow-ups

How would you recover the actual worker indices for the minimum-cost group?
What changes if workers can be paid different rates instead of one shared rate?
How would you handle a streaming version where workers arrive already sorted by ratio?
Can you explain why the heap is a max-heap even though the goal is minimum cost?

Key Takeaways

For any hired group, the largest wage-to-quality ratio determines the shared pay rate.
After sorting by ratio, the current worker can be treated as the limiting highest-ratio worker.
Under a fixed ratio, minimizing total cost means minimizing the sum of selected qualities.
A max-heap of qualities removes the largest quality so the heap keeps the **k** smallest eligible qualities.

Reusable template: Ratio-frontier greedy: sort by the limiting ratio, maintain a size-k heap that optimizes the additive quantity under the current ratio, and evaluate the objective at every valid prefix.