Minimum Cost to Hire K Workers Hard 0 attempts
LeetCode ↗

Minimum Cost to Hire K Workers

Hard HeapPriority Queue LeetCode

Given quality and wage arrays for workers, hire exactly k workers minimizing total cost. Each worker must be paid proportionally to quality and at least their minimum wage.

Example: quality=[10,20,5], wage=[70,50,30], k=2 → Output: 105.0

Sample Input
—
Sample Output
—
Constraints
  • 1 <= k <= workers <= 10^4
  • 1 <= quality[i], wage[i] <= 10^4
Topics
HeapPriority Queue

Sort by Ratio + Max-Heap

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

function mincostToHireWorkers(quality, wage, k) {
  const workers = quality.map((q,i) => [wage[i]/q, q]).sort((a,b) => a[0]-b[0]);
  const heap = []; let qualSum = 0, min = Infinity;
  for (const [ratio, q] of workers) {
    heap.push(q); qualSum += q;
    heap.sort((a,b) => b-a);
    if (heap.length > k) { qualSum -= heap.shift(); }
    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