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.

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.