You have n workers, each with a quality and a minimum wage. Hire exactly k of them such that: (1) every worker is paid at least their wage, and (2) pay is proportional to quality. Return the minimum total cost.

Engineering takeaway. This is a genuinely hard problem, and the reason is ordering. The cost formula is simple once you see it, but the greedy sweep only works if you pop the largest quality from the heap after inserting the current worker — a one-line order that's easy to get wrong. Reading this post is basically a free lesson in "the heap pop order matters."

Intuition

If a group shares one pay-per-quality ratio r, then each worker i is paid r * quality[i]. Worker i accepts only if r * quality[i] >= wage[i], i.e. r >= wage[i] / quality[i]. So for a chosen group, the ratio must be at least the maximum wage/quality among its members.

That gives the cost formula:

cost = maxRatio * sum(qualities)

where maxRatio is the largest wage/quality in the group. Now the problem becomes: sweep workers in ascending wage/quality order; at each pivot (the new maxRatio), keep the k smallest qualities among everything so far.

Approach

  1. Sort workers by wage/quality (compare via cross-multiplication to avoid floating-point drift).
  2. Maintain a max-heap of the current smallest k qualities and a running totalQuality.
  3. For each worker as the pivot:
    • insert quality and add it to totalQuality;
    • if the heap now holds more than k workers, pop the largest quality and subtract it;
    • when the heap holds exactly k, the candidate cost is ratio * totalQuality.

We implement a small MinHeap since TypeScript has no built-in heap — and use it as a max-heap by inverting the comparator.

class MinHeap<T> {
  private heap: T[] = [];
 
  constructor(private compare: (a: T, b: T) => number) {}
 
  size(): number {
    return this.heap.length;
  }
 
  private swap(i: number, j: number): void {
    [this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]];
  }
 
  private parent(i: number): number {
    return Math.floor((i - 1) / 2);
  }
 
  private up(i: number): void {
    while (i > 0 && this.compare(this.heap[i], this.heap[this.parent(i)]) < 0) {
      this.swap(i, this.parent(i));
      i = this.parent(i);
    }
  }
 
  private down(i: number): void {
    while (true) {
      const left = 2 * i + 1;
      const right = 2 * i + 2;
      let smallest = i;
 
      if (left < this.heap.length && this.compare(this.heap[left], this.heap[smallest]) < 0) {
        smallest = left;
      }
      if (right < this.heap.length && this.compare(this.heap[right], this.heap[smallest]) < 0) {
        smallest = right;
      }
 
      if (smallest === i) break;
      this.swap(i, smallest);
      i = smallest;
    }
  }
 
  insert(value: T): void {
    this.heap.push(value);
    this.up(this.heap.length - 1);
  }
 
  pop(): T {
    const min = this.heap[0];
    const last = this.heap.pop() as T;
    if (this.heap.length > 0) {
      this.heap[0] = last;
      this.down(0);
    }
    return min;
  }
}
 
type Worker = { quality: number; wage: number };
 
function minCostToHireWorkers(quality: number[], wage: number[], k: number): number {
  const workers: Worker[] = quality.map((q, i) => ({ quality: q, wage: wage[i] }));
 
  // Sort by wage/quality, comparing with cross-multiplication (exact, no floats)
  workers.sort(
    (a, b) => a.wage * b.quality - b.wage * a.quality,
  );
 
  const maxQualityHeap = new MinHeap<number>((a, b) => b - a); // max-heap of qualities
  let totalQuality = 0;
  let result = Number.POSITIVE_INFINITY;
 
  for (const worker of workers) {
    // 1. Insert the current worker FIRST
    maxQualityHeap.insert(worker.quality);
    totalQuality += worker.quality;
 
    // 2. Then, if we exceed k, evict the largest quality
    if (maxQualityHeap.size() > k) {
      totalQuality -= maxQualityHeap.pop();
    }
 
    // 3. Exactly k workers → candidate cost
    if (maxQualityHeap.size() === k) {
      const ratio = worker.wage / worker.quality;
      result = Math.min(result, ratio * totalQuality);
    }
  }
 
  return result;
}

Note the order in step 2: the current worker must be in the heap before we evict, otherwise we can't correctly keep "the k smallest qualities." Get that backwards and the maintained group drifts — the exact bug that's easy to write and hard to notice.

Complexity

  • Time: O(n log n) — the sort plus heap operations.
  • Space: O(n) — for the worker list and the heap.

The lesson

"Keep the smallest k of everything seen so far" is the canonical max-heap of size k pattern — the heap stores the worst candidates so the best k survive. It's the same machinery behind top-k lists, median maintenance, and sliding-window stats. And as this problem demonstrates, getting the pop order right is what separates a correct heap sweep from a subtle bug.