Minimum Cost to Hire K Workers

Share

Hire K workers: each must be paid at least their wage/quality ratio. Minimize total cost.

Example 1
Input: quality=[10,20,5], wage=[70,50,30], k=2 → Output: 105.0
Example 2
Input: quality=[3,1,10,10,1], wage=[4,8,2,2,7], k=3 → Output: 30.66667

Solution Approach

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
Java
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)