LeetCode 857: Minimum Cost to Hire K Workers

Problem Restatement

We are given n workers.

Each worker has:

We need to hire exactly k workers.

The payment must satisfy two rules:

1. Every hired worker must be paid at least their minimum wage.
2. In the hired group, pay must be proportional to quality.

That means if one worker has twice the quality of another worker, they must receive twice the pay.

Return the minimum total amount of money needed to hire exactly k workers.

Answers within 10^-5 of the correct answer are accepted.

Input and Output

Function shape:

class Solution:
    def mincostToHireWorkers(self, quality: list[int], wage: list[int], k: int) -> float:
        ...

Examples

Example 1:

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

Worker ratios:

If we hire workers 0 and 2, the highest wage-to-quality ratio is 7.0.

So everyone must be paid at rate 7.0 per quality.

Total cost:

70 + 35 = 105

So the answer is:

105.0

Example 2:

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

The minimum cost is:

30.66667

First Thought: Try Every Group

A direct approach is to try every group of exactly k workers.

For each group:

1. Find the highest wage-to-quality ratio in that group.
2. Use that ratio as the pay rate.
3. Compute total cost as:

rate * sum_of_quality

4. Keep the minimum total cost.

This is correct, but it is too slow because the number of possible groups can be huge.

We need a way to avoid checking every combination.

Key Insight

Because pay must be proportional to quality, every hired worker is paid using the same rate:

pay = quality * rate

For worker i to accept, we need:

quality[i] * rate >= wage[i]

So:

rate >= wage[i] / quality[i]

For a chosen group, the rate must be at least the largest ratio among that group.

So every group has a controlling worker: the worker with the highest wage / quality ratio.

If we fix that controlling ratio, the total cost becomes:

ratio * total_quality

For a fixed ratio, minimizing cost means choosing the k workers with the smallest total quality among workers whose ratio is not greater than that fixed ratio.

This gives us the strategy:

1. Sort workers by wage / quality.
2. Process workers from smallest ratio to largest ratio.
3. Treat the current worker as the highest-ratio worker in the group.
4. Among all workers seen so far, keep the k smallest qualities.
5. Compute the cost when we have exactly k workers.

Algorithm

Build a list of workers:

(ratio, quality)

where:

ratio = wage[i] / quality[i]

Sort workers by ratio.

Maintain:

quality_sum

as the sum of selected qualities.

Use a max heap to keep the k smallest qualities seen so far.

Python only has a min heap, so we store negative qualities.

For each worker in sorted order:

1. Add the worker’s quality to the heap.
2. Add the quality to quality_sum.
3. If the heap has more than k workers, remove the largest quality.
4. If the heap has exactly k workers, compute:

quality_sum * ratio

5. Keep the minimum cost.

Correctness

Sort workers by increasing wage-to-quality ratio.

When processing a worker with ratio r, all previously seen workers have ratio at most r.

Therefore, any group formed from the current worker and previously seen workers can be paid at rate r, because every worker in that group has minimum required ratio at most r.

For this fixed rate r, the total cost is:

r * total_quality

Since r is fixed, the cheapest valid group is the group with the smallest total quality among the seen workers.

The max heap maintains exactly that: the k smallest qualities among workers seen so far. If more than k workers are available, the largest quality is removed because keeping it can only increase the total cost for the same rate.

Every optimal group has some worker with the highest wage-to-quality ratio. When the algorithm reaches that worker in sorted order, all workers in the optimal group have already been seen. The heap considers the best possible k qualities among those workers, so the cost computed at that point is no worse than the optimal group using that highest ratio.

Taking the minimum over all such steps gives the global minimum cost.

Complexity

Let:

n = len(quality)

The heap stores at most k qualities.

Implementation

import heapq

class Solution:
    def mincostToHireWorkers(self, quality: list[int], wage: list[int], k: int) -> float:
        workers = []

        for q, w in zip(quality, wage):
            ratio = w / q
            workers.append((ratio, q))

        workers.sort()

        max_heap = []
        quality_sum = 0
        answer = float("inf")

        for ratio, q in workers:
            heapq.heappush(max_heap, -q)
            quality_sum += q

            if len(max_heap) > k:
                removed_quality = -heapq.heappop(max_heap)
                quality_sum -= removed_quality

            if len(max_heap) == k:
                answer = min(answer, quality_sum * ratio)

        return answer

Code Explanation

We first convert each worker into a ratio-quality pair:

for q, w in zip(quality, wage):
    ratio = w / q
    workers.append((ratio, q))

The ratio means the minimum pay rate needed by that worker.

Then we sort:

workers.sort()

Now we process possible controlling workers from lowest ratio to highest ratio.

We use a heap:

max_heap = []

Python’s heapq is a min heap. To simulate a max heap, we store negative qualities.

When adding a worker:

heapq.heappush(max_heap, -q)
quality_sum += q

If there are more than k workers, we remove the largest quality:

removed_quality = -heapq.heappop(max_heap)
quality_sum -= removed_quality

This keeps the selected total quality as small as possible.

When exactly k workers are selected, the current ratio can pay all of them:

answer = min(answer, quality_sum * ratio)

Finally, we return the minimum cost:

return answer

Testing

def test_min_cost_to_hire_workers():
    s = Solution()

    assert abs(s.mincostToHireWorkers([10, 20, 5], [70, 50, 30], 2) - 105.0) < 1e-5

    assert abs(
        s.mincostToHireWorkers(
            [3, 1, 10, 10, 1],
            [4, 8, 2, 2, 7],
            3,
        ) - 30.6666666667
    ) < 1e-5

    assert abs(s.mincostToHireWorkers([1], [5], 1) - 5.0) < 1e-5

    assert abs(s.mincostToHireWorkers([5, 10], [10, 20], 2) - 30.0) < 1e-5

    assert abs(s.mincostToHireWorkers([4, 8, 2], [8, 16, 10], 2) - 20.0) < 1e-5

    print("all tests passed")

test_min_cost_to_hire_workers()

Test meaning: