Ratio Hiring
What is this?
You are hiring a crew, and two rules bind at once: everyone is paid in proportion to how much work they do, and nobody accepts less than their stated minimum. Together these force a single pay rate for the whole crew: the rate demanded by the member with the highest minimum wage per unit of quality.
Two variables interact here (the rate and the crew's total quality). Trying every crew is hopeless, but sorting by the rate decouples them.
Why the sort works: if you hire a group, the shared rate must satisfy every member, so it equals the maximum wage-to-quality ratio in the group. Walking the list in ascending ratio order means the worker you have just reached has the highest ratio of anyone so far, so that worker is the rate for any crew drawn from the prefix. For one fixed rate the cost is the rate times the sum of the
ksmallest qualities in the prefix, and a heap maintains exactly that. It is the same move as 201's Maximum Performance of a Team, where sorting by efficiency fixes the multiplier.
🔓 The 2 problems in this chapter are free. Sign in with Google or Microsoft to start solving.
1. The algorithm
import heapq
workers = sorted((w / q, q) for q, w in zip(quality, wage)) # ascending ratio
best = float('inf')
heap, total = [], 0
for ratio, q in workers:
heapq.heappush(heap, -q) # max-heap of qualities
total += q
if len(heap) > k:
total += heapq.heappop(heap) # remove the LARGEST quality (negated)
if len(heap) == k:
best = min(best, ratio * total)
return best
Three points to defend out loud. The heap holds qualities, not wages, because once the rate is fixed the cost is rate × total quality and nothing else matters. The heap is a max-heap: you evict the largest quality, which is the expensive one, keeping the k cheapest. And the answer is recorded only when exactly k workers are held, since a smaller crew does not satisfy the requirement.
Note total += heapq.heappop(heap) rather than -=: the popped value is already negative, so adding it subtracts the quality. That sign inversion is a routine source of bugs.
The sort is the cost: O(n log n) time, and O(n) space for the sorted pairs and the heap.
2. The bounded-pool variant
Total Cost to Hire K Workers changes the shape. There is no shared rate and no sort. Each of k sessions hires the cheapest worker among the first candidates and last candidates still in the line, so only a bounded window at each end is visible. The naive version rescans both windows and deletes from the middle of the list, which is O(k * (candidates + n)) and mutates the input. Two min-heaps, one per end, give the cheapest in O(1) and a hire in O(log candidates). After each hire the end you took from refills its heap from the untouched middle.
The tie-break is part of the problem: on equal cost the lower index wins, so the front heap is preferred when the two tops are equal. Refill only while the left pointer has not passed the right pointer. When n < 2 * candidates the windows overlap, so the back window must start at max(n - candidates, candidates) or a worker lands in both heaps.
3. A 30-second worked example
quality = [10, 20, 5], wage = [70, 50, 30], k = 2.
Sorted by ratio the workers are (2.5, q=20), (6.0, q=5), (7.0, q=10). After two workers the heap holds qualities 20 and 5, so the candidate is 6.0 * 25 = 150. At the third worker the rate rises to 7.0, quality 10 is pushed and the largest quality, 20, is evicted. The heap now holds 10 and 5, and the candidate is 7.0 * 15 = 105.
The last step is the instructive one: paying a higher rate became cheaper because evicting the high-quality worker cut the total quality by more than the rate rose. That trade is invisible without the heap.
4. Where you'll actually meet this
- Piece-rate crews. One rate per unit of output, high enough for the member with the highest minimum per unit.
- Uniform-price purchasing. Buying
kunits at one price set by the most expensive accepted unit, so the bill scales with the size of what you take. - Two-ended windows. Any consumer that pulls the cheaper item from the head of one buffer or the tail of another, with only a window visible at each end, has the bounded-pool structure.
I would not claim a specific product runs these exact rules. The transferable techniques are sorting by the constraint ratio and keeping the best k in a heap, and keeping one small heap per end with a pointer into the untouched middle.
5. Problems in this chapter
Minimum Cost to Hire K Workers
Hire exactly k workers paid proportionally under one shared rate. Sort by wage/quality, keep the k smallest qualities in a max-heap, and evaluate at every step where the heap is full. For one fixed rate the cost is the sum of the k smallest qualities times that rate. The lesson starts from an O(n² log n) brute force that tries every worker as the rate-setter.
Pattern: sort to fix the rate + size-k heap. Target: O(n log n) time, O(n) space.
Total Cost to Hire K Workers
Hire k workers from the two ends of a queue with a bounded visible pool. Two heaps, refilled as each end advances, with ties going to the lower index. The naive scan-and-delete version is O(k * (candidates + n)) and mutates the input.
Pattern: dual bounded heaps with pointer refill. Target: O((k + candidates) log candidates) time, O(candidates) space.
6. Common pitfalls
- Heaping wages instead of qualities. Once the rate is fixed, cost is rate × total quality, and wages are already accounted for by the ratio.
- Using a min-heap. You evict the most expensive quality, so the heap must expose the largest.
- Recording a cost before the heap is full, which prices a crew smaller than
k. - Sign errors on the negated pop. The popped value is negative; add it rather than subtracting.
- Floating-point ratio ties. Where exactness matters, compare
w1 * q2againstw2 * q1or keep ratios asFraction(w, q). Floats are fine at the 1e-5 tolerance the lesson uses. - Crossing the pointers in the bounded-pool variant, or letting the two windows overlap when
n < 2 * candidates, which puts one worker in both heaps so they can be hired twice. - Getting the tie-break backwards. Equal cost means the lower index, so the front heap wins (
<=on the tops).
7. Key takeaways
- Sort to fix one variable. Ascending ratio makes the current worker the rate for the whole prefix.
- Then minimise what is left, total quality, which is exactly what a size-
kheap does. - Evict the largest, so the heap must be a max-heap.
- Evaluate only at full size. A partial crew is not a candidate answer.
- A higher rate can be cheaper if it lets you drop an expensive member; the heap is what finds that.
- Cross-multiply instead of dividing when ratio ties need exactness.
- Bounded pools need two heaps and a pointer check, with ties to the lower index.
- Why it is a good interview problem: the greedy is not obvious and the proof is short, so it separates candidates who can justify a sort order from those who try every subset.
Order: Minimum Cost to Hire K Workers → Total Cost to Hire K Workers.