Minimum Cost to Hire K Workers Hard 0 attempts
LeetCode ↗

Minimum Cost to Hire K Workers

Hard HeapPriority Queue LeetCode

You're given two arrays, quality and wage, describing a pool of workers, plus a target headcount k. Form a group of exactly k workers while paying as little in total as possible. Within the hired group, pay must stay proportional to each worker's quality score, and no one can be paid less than the minimum wage they listed.

Input Format
Implement mincostToHireWorkers(quality, wage, k). Inputs below show JavaScript function arguments; there is no stdin parsing.
Output Format
Return the result described in the statement. Floating-point results are compared with relative tolerance 0.00001.

Sample Input and Output

Example 1 ยท Run Sample

Input
quality = [10,20,5]
wage = [70,50,30]
k = 2
Output
105

Example 2

Input
quality = [3,1,10,10,1]
wage = [4,8,2,2,7]
k = 3
Output
30.6666666667
Constraints
  • 1 <= k <= workers <= 10^4
  • 1 <= quality[i], wage[i] <= 10^4
Test Cases (2)
Case 1
Args: [[10,20,5],[70,50,30],2] Expected: 105
Case 2
Args: [[3,1,10,10,1],[4,8,2,2,7],3] Expected: 30.6666666667
Topics
HeapPriority Queue

Sort by Ratio + Max-Heap

Sort by wage/quality ratio. Use max-heap to maintain k smallest qualities.

javascript
function mincostToHireWorkers(quality, wage, k) {
  const workers = quality.map((q,i) => [wage[i]/q, q]).sort((a,b) => a[0]-b[0]);

  const heap = [];
  function push(value) {
    heap.push(value); let i = heap.length - 1;
    while (i > 0) {
      const p = Math.floor((i-1)/2); if (heap[p] >= heap[i]) break;
      [heap[p],heap[i]] = [heap[i],heap[p]]; i = p;
    }
  }
  function pop() {
    const max = heap[0], last = heap.pop();
    if (heap.length) {
      heap[0] = last; let i = 0;
      while (2*i+1 < heap.length) {
        let child = 2*i+1;
        if (child+1 < heap.length && heap[child+1] > heap[child]) child++;
        if (heap[i] >= heap[child]) break;
        [heap[i],heap[child]] = [heap[child],heap[i]]; i = child;
      }
    }
    return max;
  }
  let qualSum = 0, min = Infinity;
  for (const [ratio, q] of workers) {
    push(q); qualSum += q;
    if (heap.length > k) { qualSum -= pop(); }
    if (heap.length === k) min = Math.min(min, qualSum * ratio);
  }
  return min;
}

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

Saved in this browser only. Private to you.

JavaScript