</> MAANG.io

Advanced

Advanced problems where modelling is the hard part: implicit graphs, tricky DP states, intervals and design challenges.

0 of 95 solved 0%

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.

Ratio hiring reduced from two coupled costs to one heaped variable

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 k smallest 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.

Worked example: hiring 2 of 3 workers, answer 105

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 k units 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 * q2 against w2 * q1 or keep ratios as Fraction(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

  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. Bounded pools need two heaps and a pointer check, with ties to the lower index.
  8. 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.

Minimum Cost to Hire K Workers

Core idea: Within any hired group, the pay rate is forced to be the largest wage-per-quality ratio in the group. So fix each worker as the one who sets that rate, then pay everyone by quality, which means you want the k smallest qualities seen at that rate. Sort by ratio, sweep, and keep those k qualities in a max-heap so you can always evict the biggest one.

Problem, rephrased

You're staffing a project and must hire exactly k workers from a pool of n. You're given two integer arrays, quality and wage, where quality[i] is how much worker i produces and wage[i] is the minimum total pay that worker will accept, plus the integer k.

Sign in to continue reading

The rest of this lesson is available with a free account. Signing in with Google or Microsoft is free.

Sign in to read the full lesson

Sign in to MAANG.io

Use your Google or Microsoft account — no password to remember.

Continue with Google Continue with Microsoft

Please accept the terms above to continue.