AlgoMaster Logo

Minimum Cost to Hire K Workers

hardFrequency7 min readUpdated June 23, 2026

Understanding the Problem

We need to pick exactly k workers from a pool of n workers. Two rules pull in opposite directions. Rule 1 says every worker must be paid at least their minimum wage. Rule 2 says pay must be proportional to quality. If we fix a single "rate per unit of quality" for the group, every worker in it is paid rate * quality[i].

A high rate satisfies everyone's minimum wage but raises the total cost. A low rate fails some worker's minimum wage and disqualifies that worker. For a fixed group, the smallest rate that keeps everyone above their minimum wage is set by the most demanding worker, the one with the highest wage[i] / quality[i] ratio.

That reframes the problem. For each possible "captain" (the worker whose ratio sets the pay rate), find the cheapest set of k workers whose ratios are all at or below the captain's ratio. Pay is rate * quality[i] and the rate is fixed by the captain, so we want the k workers with the smallest total quality among those with acceptable ratios. A max-heap tracks those k smallest qualities.

Key Constraints:

  • 1 <= k <= n <= 10^4 → With n up to 10,000, an O(n^2) scan over subsets or pairs is at the edge of acceptable and enumerating subsets is impossible. The sorting plus heap approach runs in O(n log n).
  • 1 <= quality[i], wage[i] <= 10^4 → The largest total quality is 10^4 * 10^4 = 10^8, and a ratio can be as high as 10^4, so the cost can reach roughly 10^12. That exceeds a 32-bit int, so the cost must be a double (or 64-bit) and the quality sum fits in a 32-bit int only up to 10^8, which is safe.

Approach 1: Brute Force (Try All Subsets)

Intuition

Try every possible combination of k workers. For each subset, find 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

Enumerating every subset is impractical for n much larger than 20. The next approach avoids enumeration by fixing the rate first, then choosing the cheapest workers under that rate.

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

Intuition

For any group of workers, the total cost factors cleanly into two parts:

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

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

Sort all workers by their ratio wage[i] / quality[i] in ascending order. If worker j is the captain (the highest ratio in the group), then every worker before j in sorted order has a ratio at or below j's ratio. All of them can be hired at j's rate without violating their minimum wage, so they are eligible.

For each worker j in sorted ratio order, the eligible pool is workers 0, 1, ..., j. The rate is already fixed at ratio[j], so we pick the k workers (including j) with the smallest total quality. The cost becomes ratio[j] * (sum of the k smallest qualities among workers 0..j).

A max-heap of size k tracks the k smallest qualities as we iterate. The heap holds the k smallest qualities seen so far. When a new worker's quality is smaller than the heap's maximum, the maximum is evicted and the new value takes its place. The heap then holds 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
maxHeap (qualities)
1Max-heap empty. About to process first worker.
[]
minCost
1minCost = Infinity (no group formed yet)
Infinity
1/6

Code