AlgoMaster Logo

Minimum Cost to Hire K Workers

Last Updated: March 29, 2026

hard
5 min read

Understanding the Problem

We need to pick exactly k workers from a pool of n workers. The tricky part is the two rules pulling in different directions. Rule 1 says every worker must be paid at least their minimum wage. Rule 2 says pay must be proportional to quality. So if we decide on a "rate per unit of quality," every worker in our group gets paid rate * quality[i].

Here is the core tension. If we pick a high rate, we satisfy everyone's minimum wage easily, but the total cost goes up. If we pick a low rate, some workers won't meet their minimum wage and can't be in the group. The rate is essentially determined by the "pickiest" worker in the group, the one with the highest ratio of wage[i] / quality[i].

So the problem boils down to: for each possible "captain" (the worker whose wage-to-quality ratio sets the pay rate), find the cheapest set of k workers whose ratios are all at or below the captain's ratio. Since pay is rate * quality[i], and the rate is fixed by the captain, we want the k workers with the smallest total quality among those with acceptable ratios. That is where a max-heap comes in.

Key Constraints:

  • 1 <= k <= n <= 10^4 → With n up to 10,000, we need O(n^2) or better. An O(n log n) approach using sorting and a heap is ideal.
  • 1 <= quality[i], wage[i] <= 10^4 → Values are moderate. The maximum possible total cost is about 10^4 workers * 10^4 wage = 10^8, which fits comfortably in a double.

Approach 1: Brute Force (Try All Subsets)

Intuition

The most direct approach is to try every possible combination of k workers. For each subset, figure out the minimum valid pay rate and compute the total cost.

For any group of k workers, the pay rate must be high enough to satisfy every worker's minimum wage. Since each worker's pay is rate * quality[i], they need rate * quality[i] >= wage[i], which means rate >= wage[i] / quality[i]. The minimum valid rate for the group is the maximum of wage[i] / quality[i] across all workers in the group. Once we know the rate, the total cost is rate * (sum of all qualities in the group).

So we enumerate all C(n, k) subsets, compute the required rate and total cost for each, and return the minimum.

Algorithm

  1. Compute ratio[i] = wage[i] / quality[i] for each worker.
  2. Generate all combinations of k workers from the n available.
  3. For each combination, find the maximum ratio in the group (this is the rate).
  4. Compute the total cost as rate * sum(quality[i]) for workers in the group.
  5. Track and return the minimum total cost across all combinations.

Example Walkthrough

Input:

0
10
1
20
2
5
quality
0
70
1
50
2
30
wage

We try all C(3,2) = 3 subsets:

  • {W0, W1}: maxRatio = max(7.0, 2.5) = 7.0, totalQuality = 30, cost = 210.0
  • {W0, W2}: maxRatio = max(7.0, 6.0) = 7.0, totalQuality = 15, cost = 105.0
  • {W1, W2}: maxRatio = max(2.5, 6.0) = 6.0, totalQuality = 25, cost = 150.0
105
minCost

Code

This approach tries every possible subset, which is impractical for n > 20. What if we could process workers in a smart order that lets us incrementally build the best group?

Approach 2: Sort by Ratio + Greedy with Max-Heap

Intuition

Here is the key insight that unlocks this problem. For any group of workers, the total cost is:

cost = (max ratio in group) * (sum of qualities in group)

The "max ratio" is the wage-to-quality ratio of the most expensive worker (per unit of quality) in the group. That worker is the bottleneck, the one who forces the pay rate up for everyone.

Now think about it from a different angle. Imagine we sort all workers by their ratio wage[i] / quality[i] in ascending order. If we pick worker j as the "captain" (the one with the highest ratio in our group), then every worker before j in sorted order has a ratio less than or equal to j's ratio. That means they can all be hired at j's rate without violating their minimum wage. They are all eligible candidates for our group.

So for each worker j (considered in sorted ratio order), the eligible pool is workers 0, 1, ..., j. Among these, we want to pick k workers (including j) that minimize the total quality, since the rate is already fixed at ratio[j]. The cost becomes ratio[j] * (sum of the k smallest qualities among workers 0..j).

How do we efficiently track the k smallest qualities as we iterate? A max-heap of size k does the job. We maintain a heap of the k smallest qualities seen so far. As we process each new worker, if their quality is smaller than the largest in the heap, we swap them in. This way, the heap always contains the k workers with the smallest total quality among all eligible workers.

Algorithm

  1. For each worker, compute their ratio wage[i] / quality[i].
  2. Create an array of worker indices and sort it by ratio in ascending order.
  3. Initialize a max-heap (priority queue) and a running sum of qualities (qualitySum).
  4. Iterate through workers in sorted ratio order:
    • Add the current worker's quality to the heap and to qualitySum.
    • If the heap size exceeds k, remove the largest quality from the heap and subtract it from qualitySum.
    • If the heap size equals k, compute cost = ratio[current] * qualitySum and update the minimum.
  5. Return the minimum cost found.

Example Walkthrough

1Sorted by ratio: W1(ratio=2.5, q=20), W2(ratio=6.0, q=5), W0(ratio=7.0, q=10)
0
20
process
1
5
2
10
1/6
1Max-heap empty. About to process first worker.
[]
1/6
1minCost = Infinity (no group formed yet)
Infinity
1/6

Code