Minimum cost to hire K workers in Python

Why this matters

A project manager needs a team of exactly K workers. Each worker has a quality score, which measures how much useful work they do, and a minimum wage, which is the least they will accept. The manager wants the team that costs the least while still being fair to everyone on it.

The fairness rule is the hard part. Suppose a worker with quality 10 accepts a wage of 70, and a worker with quality 5 accepts 30. The first worker needs 7 per quality point and the second needs 6. If the manager pays both at 6 per point, the first worker is short. Both must be paid at 7 per point. The rule that makes this fair is: every worker is paid in proportion to their quality, at one shared rate, and every worker is paid at least their minimum wage.

This is a greedy problem in disguise. The choice that matters is which worker sets the pay rate for the whole team. Once that is fixed, the best team is simply the K workers with the smallest quality that fit under that rate. A heap is a data structure that gives you the smallest item quickly. Python's heapq module provides one, and it makes the search fast.

This lesson builds the solution from a plain example. It adds one new tool: heapq, the standard library module for heaps.

The rules in plain words

Each worker i has a quality quality[i] and a minimum wage wage[i]. The manager chooses a group of K workers and pays them.

Two rules apply to the pay.

1. Pay in proportion to quality. Choose one pay rate r, and pay each worker in the group r * quality[i]. The pay per quality point is the same for everyone.
2. Pay at least the minimum wage. Each worker must get at least wage[i]. So r * quality[i] must be at least wage[i], which means r must be at least wage[i] / quality[i].

Look at the second rule carefully. Every worker in the group needs r to be at least their own ratio wage[i] / quality[i]. To satisfy all of them, r must be at least the largest ratio in the group. The cheapest fair choice is to set r equal to that largest ratio.

The total cost of the group is then:

cost = (largest ratio in the group) * (sum of qualities in the group)

The job is to pick the group of K workers that makes this number as small as possible.

Example one: three workers, K equals 2

Use three workers:

There are three ways to choose two workers. For each pair, the rate is the largest ratio in the pair, and the cost is that rate times the sum of the two qualities.

The cheapest is workers 0 and 2, at 105. Worker 0 gets 7 times 10, which is 70, exactly their minimum. Worker 2 gets 7 times 5, which is 35. That is more than their minimum of 30, which is allowed.

Checking every pair works for three workers. For a thousand workers, the number of groups is far too large to check one by one. The next sections show a faster way.

Exact ratios with Fraction

The ratios in this lesson are not always whole numbers. Worker 1 has a ratio of 2.5, and a ratio like 92 / 3 has no exact decimal form. A float (Python's usual decimal number type) stores a close approximation, and small rounding errors can change which worker sorts first when two ratios are very close.

The fractions module avoids this. Fraction(wage, quality) stores the ratio as an exact pair of whole numbers, and arithmetic on it stays exact:

from fractions import Fraction
 
print(Fraction(5, 2))
print(Fraction(1, 3) * 3 == 1)
print(Fraction(92, 3))
print(float(Fraction(92, 3)))

Output:

5/2
True
92/3
30.666666666666668

Python integers have no size limit, so the product wage[a] * quality[b] cannot overflow. Java needs a long for that product in the same place. Python does not need that step.

The key idea: sort by ratio

Sort the workers by their ratio, smallest first. The ratios for the three workers above are 5/2 (worker 1), 6 (worker 2) and 7 (worker 0). The sorted order is worker 1, then worker 2, then worker 0.

The code sorts indexes, not the workers themselves:

order = sorted(range(n), key=lambda i: Fraction(wage[i], quality[i]))

range(n) gives the numbers 0 to n - 1. sorted returns a new list of those numbers. The key function says what to compare: the exact ratio of worker i. The lambda i: ... part is a short unnamed function that takes i and returns that ratio.

Now walk through the sorted list. When you reach a worker, call that worker the rate setter. Its ratio is the largest so far, so it sets the pay rate for every worker seen up to this point. The group must include the rate setter, and the other K - 1 workers come from the workers before it in the list.

Here is the catch. The rate setter's ratio is only the largest if the rate setter is in the group. But if the program picks a group that does not include the rate setter, the rate setter's ratio is still at least as large as every other ratio in the group. So the cost computed with that ratio is never too low. It is a price that can really be paid. That means every value the program computes is a real, achievable cost, and the smallest one is the answer.

To find the smallest quality sum, the program needs the K workers with the smallest quality among those seen so far. The tool for this is a heap that keeps the largest quality on top, so the program can remove it. Python's heapq only builds min heaps, where the smallest item is on top. The fix is to store negative qualities. The smallest negative number is the one with the largest size, so the top of the min heap is the largest quality.

import heapq
 
heap = []
for q in [20, 5, 10]:
    heapq.heappush(heap, -q)
print(heap)
top = -heapq.heappop(heap)
print(top)
print(heap)

Output:

[-20, -5, -10]
20
[-10, -5]

heappush adds an item and keeps the heap in order. heappop removes and returns the smallest item. Here the stored values are negative, so heappop returns -20, and the program flips the sign back to get the quality 20.

Each time the heap holds exactly K workers, the program computes a cost: the current ratio times the running sum of qualities in the heap. It keeps the smallest cost seen.

Working through example one by hand

Process the sorted list, with K equal to 2. The table shows the real quality values, although the heap stores them as negatives.

At step 2 the cost is 150, which uses workers 1 and 2. At step 3 the heap has three items, so the program removes the largest quality, 20, leaving workers 2 and 0. The rate is 7 and the sum is 15, so the cost is 105. The smallest cost over the steps is 105, which matches the cheapest pair in the pair table above.

The Python program

The program below has three parts. min_cost is the fast method. brute tries every group of K workers, using itertools.combinations, which yields each group once. The bottom part runs both methods on 2,000 random inputs and counts disagreements.

Save the program as hire_workers.py, then run it with:

python3 hire_workers.py

The output on Python 3.14 is:

105
30.666666666666668
random mismatches: 0

The first line is example one. Fraction prints a whole number without a decimal point, so the cost is 105, not 105.0. The second line is a larger example with five workers and K equal to 3. Its exact answer is 92 / 3, which is 30.666..., and float prints the nearest double, 30.666666666666668. The last line compares the fast method with brute force on 2,000 random inputs of up to nine workers. No input disagreed. The random inputs come from random.Random(42). Other Python versions can produce a different sequence, but the count should still be 0.

The if __name__ == "__main__": line means the test code runs only when you run the file directly. If you import min_cost from another file, the tests do not run.

A second example, with five workers

Take five workers, K equal to 3:

• Quality: 3, 1, 10, 10, 1
• Minimum wage: 4, 8, 2, 2, 7

The ratios are 4/3 for worker 0, 8 for worker 1, 1/5 for worker 2, 1/5 for worker 3, and 7 for worker 4. Sorted, the order is worker 2 and worker 3 (both 1/5), then worker 0 (4/3), then worker 4 (7), then worker 1 (8).

The best group is workers 2, 3 and 0. Their qualities add to 23, and their largest ratio is 4/3. The cost is 4/3 times 23, which is 92/3, or 30.67. The program reaches this answer when it processes worker 0, the third worker in sorted order. The heap then holds the qualities 10, 10 and 3.

The point of this example is that the ratio decides the group, not the wage alone. Workers 2 and 3 each have a high quality (10) for a low wage (2), so they are good value. Worker 1 has the highest wage per quality point and is never part of the cheapest group.

Common mistakes

Using heapq as a max heap without negating. heapq is a min heap, so heappush(heap, quality) puts the smallest quality on top. Popping then removes the worst worker, and the heap keeps the largest qualities, which is the opposite of what the cost needs. On example one, a version without the minus signs prints 150 instead of 105. The wrong program runs without any error, so the mistake only shows in the answer.

Forgetting to remove the largest quality. If the program adds every worker to the heap and never pops one, the heap holds more than K items. The check len(heap) == k then rarely becomes true, and the sum includes too many workers. On example one, the version that never pops also prints 150, because it only computes a cost at step 2.

Calling min_cost with K larger than the number of workers. No group of that size exists, so the function returns None. The None value does not raise an error where it is returned. The error appears later, when the value is used in arithmetic:

from hire_workers import min_cost
 
result = min_cost([10, 20, 5], [70, 50, 30], 4)
print(result)
print(result * 2)

Output, from a file named try_k.py that holds this code:

None
Traceback (most recent call last):
  File "try_k.py", line 5, in <module>
    print(result * 2)
          ~~~~~~~^~~
TypeError: unsupported operand type(s) for *: 'NoneType' and 'int'

Check K against the number of workers before you call the function.

A worker with quality 0. The ratio wage / quality divides by zero. A worker with quality 0 is not a valid input. Python reports this as:

ZeroDivisionError: Fraction(3, 0)

The number in the message is the numerator, here the wage. The fix is to reject quality 0 before the sort, with a clear error message.

Sorting a range with .sort. A range object cannot be sorted in place. This is a common slip for people who write order = range(n) and then sort it:

order = range(3).sort(key=lambda i: i)

Output:

AttributeError: 'range' object has no attribute 'sort'. Did you mean: 'start'?

Use sorted(range(3), key=...), which returns a new list.

Popping from an empty heap. heapq.heappop on an empty list raises an error. The code above only pops when the heap has more than K items, so it never pops an empty heap. A change that pops first would hit this:

IndexError: index out of range

Practice

Try each exercise on paper first. Then run the program to check your answer.

1. Find the minimum cost to hire K equal to 1 from the workers in example one (quality 10, 20, 5 and minimum wage 70, 50, 30).

Show the answer

The cost is 30. With one worker, the rate is that worker's own ratio, so the pay equals the minimum wage. The cheapest single worker is worker 2, with a minimum wage of 30.

2. The workers have qualities 4, 6 and 8, and minimum wages 8, 12 and 16. Every worker has the same ratio, which is 2. Predict the minimum cost for K equal to 2, then check it.

Show the answer

The cost is 20. Every pair has rate 2, and the cheapest pair is qualities 4 and 6, with sum 10. The cost is 2 times 10, which is 20.

3. For example one with K equal to 2, explain which two workers make the cheapest team, and what each worker is paid.

Show the answer

Workers 0 and 2 make the cheapest team, at 105. The rate is 7, set by worker 0, because worker 0 has the largest ratio of the two. Worker 0 is paid 7 times 10, which is 70. Worker 2 is paid 7 times 5, which is 35, which is above their minimum of 30.

4. Remove the minus signs from the heap, so it stores plain qualities again. Predict the output for example one. Then run it.

Show the answer

The output is 150. The min heap removes the smallest quality instead of the largest. At step 3 the heap holds 20, 5 and 10, and removing the smallest leaves 20 and 10, with sum 30. The cost is 7 times 30, which is 210. The best earlier cost, 150 from step 2, is smaller, so the program returns 150.

5. Change min_cost so it returns the chosen workers as well as the cost. Explain what you would store in the heap and where to save the best group.

Show the answer

Store a tuple (-quality[i], i) in the heap, not a bare number. A tuple compares by its first item, so the heap still orders by quality, and the second item keeps the worker's index. When a new best cost is found, copy the indexes currently in the heap into a list, and return that list with the best cost. Tuples with equal first items compare by the index, which is fine for this problem.

Summary

• Each worker in a group is paid the same rate per quality point. The rate must be at least the largest wage-to-quality ratio in the group.
• Sort workers by their ratio, using exact Fraction keys. Treat each worker in turn as the rate setter, since its ratio is the largest seen so far.
• heapq builds min heaps only. Store negative qualities to keep the largest quality on top, and remove it whenever the heap goes over K.
• Each time the heap holds K workers, the cost is the current ratio times the running quality sum. The answer is the smallest cost seen.