Minimum Cost to Hire K Workers

1. Define the problem

There are n workers. You are given two arrays quality and wage, where quality_i is the quality of the ith worker and wage_i is the minimum wage expectation for the ith worker. You must hire exactly k workers to form a paid group, following these rules: every worker in the group must be paid in proportion to their quality , relative to the other workers in that group, and every worker in the group must be paid at least their minimum wage expectation. Return the least amount of money needed to form a group with these requirements. The proportional-pay rule forces a hidden structure: for any hired group, every worker's pay equals their quality times a single shared rate — and that rate is set by whichever hired worker demands the highest wage-to-quality ratio . So sort workers by that ratio ascending, and consider each one in turn as the "most expensive" member of a candidate group made from itself and the k - 1 cheapest-quality workers seen so far — tracked with a max-heap of qualities , so the most expensive-quality worker can be dropped instantly whenever the group would exceed size k.

Constraints

n == quality.length == wage.length
1 ≤ k ≤ n ≤ 10⁴
1 ≤ quality_i, wage_i ≤ 10⁴

Example

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

Output105.00000

Explanation Hire workers 0 and 2, paying them 4.7 and 2.3 per unit of quality respectively (matching worker 0's ratio 7 is not needed since worker 2's ratio 6 is what sets the group here) — the minimum-cost group turns out to be workers 0 and 2 at a rate of 7 per unit quality: 10 * 7 + 5 * 7 = 105.

2. Know the words first

In plain terms

Wage-to-quality ratio: How much a worker demands to be paid per unit of quality — the rate that everyone else in their group would also have to be paid at, if that worker is included.

3. Visualize the solution

Sort by pay ratio, maintain a max-heap of the cheapest qualities

w1 q20

w2 q5

w0 q10

Statusinit

quality=[10,20,5], wage=[70,50,30]. Ratios: worker0=7.0, worker1=2.5, worker2=6.0. Sorted by ratio: worker1(2.5), worker2(6.0), worker0(7.0).

What happens in this step

ratios: 70/10 = 7.0 (worker 0), 50/20 = 2.5 (worker 1), 30/5 = 6.0 (worker 2)
sorted order by ratio ascending: worker 1 (2.5), worker 2 (6.0), worker 0 (7.0)

Step 1 of 5

Steps to visualize

Compute each worker's wage-to-quality ratio and sort workers by that ratio ascending.
Walk workers in that order, treating each one as the most expensive ratio allowed so far (every previous worker's ratio is no larger).
Push the current worker's quality onto a max-heap and add it to a running quality sum.
If the heap grows past k workers, pop the largest quality out (cheapest workers stay), subtracting it from the running sum.
Whenever the heap holds exactly k workers, the cost of that group is the quality sum times the current ratio — track the minimum such cost.

4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Sort by pay ratio, maintain a max-heap of the cheapest qualities

w1 q20

w2 q5

w0 q10

Statusinit

quality=[10,20,5], wage=[70,50,30]. Ratios: worker0=7.0, worker1=2.5, worker2=6.0. Sorted by ratio: worker1(2.5), worker2(6.0), worker0(7.0).

What happens in this step

ratios: 70/10 = 7.0 (worker 0), 50/20 = 2.5 (worker 1), 30/5 = 6.0 (worker 2)
sorted order by ratio ascending: worker 1 (2.5), worker 2 (6.0), worker 0 (7.0)

Step 1 of 5

5. Solution

Solution

solution.tsTypeScript

function mincostToHireWorkers(quality, wage, k) {
  const n = quality.length;
  const workers = Array.from({ length: n }, (_, i) => [wage[i] / quality[i], quality[i]]);
  workers.sort((a, b) => a[0] - b[0]);

  const heap = [];

  const heapPush = (value) => {
    heap.push(value);
    let i = heap.length - 1;
    while (i > 0) {
      const parent = (i - 1) >> 1;
      if (heap[parent] >= heap[i]) {
        break;
      }
      [heap[parent], heap[i]] = [heap[i], heap[parent]];
      i = parent;
    }
  };

  const heapPop = () => {
    const top = heap[0];
    const last = heap.pop();
    if (heap.length > 0) {
      heap[0] = last;
      let i = 0;
      while (true) {
        const left = 2 * i + 1;
        const right = 2 * i + 2;
        let largest = i;
        if (left < heap.length && heap[left] > heap[largest]) {
          largest = left;
        }
        if (right < heap.length && heap[right] > heap[largest]) {
          largest = right;
        }
        if (largest === i) {
          break;
        }
        [heap[i], heap[largest]] = [heap[largest], heap[i]];
        i = largest;
      }
    }
    return top;
  };

  let qualitySum = 0;
  let best = Infinity;

  for (const [ratio, q] of workers) {
    heapPush(q);
    qualitySum += q;

    if (heap.length > k) {
      qualitySum -= heapPop();
    }

    if (heap.length === k) {
      best = Math.min(best, qualitySum * ratio);
    }
  }

  return best;
}

Time: O(n log n)
Space: O(n)

6. Test cases

Test cases

Input	Expected	Covers
`quality = [10, 20, 5], wage = [70, 50, 30], k = 2`	`105`	example from the docstring
`quality = [1], wage = [10], k = 1`	`10`	smallest valid input: a single worker hired alone
`quality = [3, 3, 3], wage = [4, 5, 6], k = 2`	`10`	equal qualities so the ratio ordering alone decides the answer
`quality = [4, 8], wage = [40, 40], k = 2`	`120`	hiring every available worker at once, so the highest ratio in the group sets the pay rate for both
`quality = [1, 3, 10], wage = [4, 6, 10], k = 2`	`16`	a high-quality worker with the most favorable ratio should anchor the cheapest group
`quality = [5, 5, 5, 5], wage = [50, 10, 20, 30], k = 3`	`90`	a wide spread of wage demands over identical qualities

Minimum Cost to Hire K Workers