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 greediest member relative to their output.

That is two variables interacting, which is exactly what makes the naive approach hopeless and the sorted approach easy.

💡 Fun fact: the reason sorting by ratio works is worth stating precisely. 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. The two-variable optimisation collapses into "minimise total quality", which a heap does trivially. It is the same manoeuvre 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.

The one-line idea: sort by the ratio so the current element fixes the rate, then use a heap to minimise the only quantity still free. Two interacting variables become one.

1. The algorithm

workers = sorted((w / q, q) for q, w in zip(quality, wage))   # ascending ratio
heap, total, best = [], 0, float('inf')
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.

2. The bounded-pool variant

Total Cost to Hire K Workers changes the shape: candidates are taken from the front and back of a queue, with only a bounded number visible from each end. Two heaps — one per end — hold the visible candidates, and after each hire the corresponding end advances and refills its heap.

The tie-break is stated and must be respected: on equal cost the lower index wins, which means the front heap is preferred when the two tops are equal. And the pointers must never cross — once they meet, all remaining candidates are already in the heaps and no refilling should occur.

3. A 30-second worked example

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

ratios:  worker0 70/10 = 7.0     worker1 50/20 = 2.5     worker2 30/5 = 6.0
sorted:  (2.5, q=20)   (6.0, q=5)   (7.0, q=10)

(2.5, 20)  heap=[20]        total=20   size 1 < k
(6.0,  5)  heap=[20,5]      total=25   size 2 = k → cost = 6.0 x 25 = 150
(7.0, 10)  heap=[20,5,10]   total=35   size 3 > k → evict 20 → total=15
                                        size 2 = k → cost = 7.0 x 15 = 105  ✅

answer = 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

• Contract and gig pricing. Group rates where one member's minimum sets the floor for everyone.
• Cloud instance selection. Choosing a fleet under a shared price tier, minimising total capacity purchased.
• Freight and logistics. Load allocation where a single per-unit rate applies across the whole shipment.
• Auction and procurement systems. Uniform-price clearing, where the marginal bid sets the price for all winners.
• Hiring pipelines. The bounded-pool variant is literally how batched candidate selection from two ends of a ranked queue is implemented.

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 cheapest qualities in a max-heap, and evaluate at every step where the heap is full.
Pattern: sort to fix the rate + size-k heap. Target: O(n log n) time, O(k) 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.
Pattern: dual bounded heaps with pointer refill. Target: O((k + candidates) log candidates).

6. Common pitfalls 🚫

• Heaping wages instead of qualities. Once the rate is fixed, cost is rate × total quality — 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 precision is tight, compare w1 * q2 against w2 * q1 instead of dividing.
• Crossing the pointers in the bounded-pool variant, which hires the same candidate twice.
• Getting the tie-break backwards — equal cost means the lower index, so the front heap wins.

7. Key takeaways

1. Sort to fix one variable. Ascending ratio makes the current worker the rate for the whole prefix.
2. Then minimise what is left — total quality — which is exactly what a size-k heap does.
3. Evict the largest, so the heap must be a max-heap.
4. Evaluate only at full size. A partial crew is not a candidate answer.
5. A higher rate can be cheaper if it lets you drop an expensive member; the heap is what finds that.
6. Cross-multiply instead of dividing when ratio ties need exactness.
7. Why interviewers like it: 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.