Hire K workers: each must be paid at least their wage/quality ratio. Minimize total cost.
Input: quality=[10,20,5], wage=[70,50,30], k=2 → Output: 105.0
Input: quality=[3,1,10,10,1], wage=[4,8,2,2,7], k=3 → Output: 30.66667
Sort by wage/quality ratio. For each ratio as the minimum, pick k smallest quality workers.
- Sort workers by wage[i]/quality[i] ratio
- Use max-heap of quality values of current group
- For each worker: add to heap, sum quality
- If heap size > k: remove highest quality
- Cost = ratio * sumQuality; track minimum
public double mincostToHireWorkers(int[] quality, int[] wage, int k) {
int n = quality.length;
double[][] workers = new double[n][2];
for (int i = 0; i < n; i++) workers[i] = new double[]{(double)wage[i]/quality[i], quality[i]};
Arrays.sort(workers, (a,b)->Double.compare(a[0],b[0]));
PriorityQueue<Double> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
double sumQ = 0, ans = Double.MAX_VALUE;
for (double[] w : workers) {
maxHeap.offer(w[1]); sumQ += w[1];
if (maxHeap.size() > k) sumQ -= maxHeap.poll();
if (maxHeap.size() == k) ans = Math.min(ans, w[0] * sumQ);
}
return ans;
}
- Time Complexity: O(n log n)
- Space Complexity: O(k)