Minimum Cost to Hire K Workers

Master this topic with zero to advance depth.

Minimum Cost to Hire K Workers

There are n workers. You are given two integer 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.

We want to hire exactly k workers to form a paid group. To hire a group of k workers, we must pay them according to the following rules:

Every worker in the paid group should be paid in the ratio of their quality compared to other workers in the paid group.
Every worker in the paid group must be paid at least their minimum wage expectation.

Return the least amount of money needed to form a paid group satisfying the above conditions.

Visual Representation

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

Ratios (wage/quality):
Worker 0: 70/10 = 7.0
Worker 1: 50/20 = 2.5
Worker 2: 30/5 = 6.0

Sorted by ratio:
[W1(2.5, q:20), W2(6.0, q:5), W0(7.0, q:10)]

To hire W2 and W1, base ratio is 6.0.
Cost = 6.0 * (20 + 5) = 150.0

To hire W0 and W2, base ratio is 7.0.
Cost = 7.0 * (10 + 5) = 105.0
Min cost = 105.0

Hard

Examples

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

Input: quality = [3,1,10,10,1], wage = [4,8,2,2,7], k = 3
Output: 30.66667

Approach 1

Level I: Sort by Ratio and Brute Force K-Smallest

Intuition

The total pay for K workers is determined by the highest wage / quality ratio among the chosen K workers. If we sort workers by this ratio, when we consider the i-th worker in the sorted list as having the maximum ratio, any K-1 workers before i can be hired at this ratio. To minimize cost, we should simply pick the K-1 workers with the smallest qualities from 0 to i-1.

Thought Process

Pair each worker's quality with their wage/quality ratio.
Sort all workers by their ratio in ascending order.
Iterate i from k - 1 to n - 1 (a valid window to pick k workers).
For each i, the ratio is worker[i].ratio.
We need to pick k qualities from index 0 to i (including worker[i].quality) that are the smallest. Since worker[i] must be included, we pick worker[i].quality + k-1 smallest qualities from 0 to i-1.
For a brute force approach, extract all qualities from 0 to i, sort them, sum the first k, and multiply by the ratio.
Keep track of the minimum cost.

⏱ O(N^2 log N) because for each of the N elements, we sort an array of size up to N💾 O(N) to store the workers and temporary arrays

Detailed Dry Run

quality = [10,20,5], wage = [70,50,30], k = 2 Ratios sorted: [(2.5,20), (6.0,5), (7.0,10)]

i=1 (ratio=6.0, q=5). We need 2 qualities from idx 0 to 1. Qualities: [20, 5]. Sorted: [5, 20]. Sum = 25. Cost = 6.0 * 25 = 150.0. Min = 150.0
i=2 (ratio=7.0, q=10). We need 2 qualities from idx 0 to 2. Qualities: [20, 5, 10]. Sorted: [5, 10, 20]. Sum = 5 + 10 = 15. Cost = 7.0 * 15 = 105.0. Min = 105.0

java

import java.util.*;

public class Main {
    static class Worker {
        double ratio;
        int quality;
        public Worker(double r, int q) { ratio = r; quality = q; }
    }
    
    public static double mincostToHireWorkers(int[] quality, int[] wage, int k) {
        int n = quality.length;
        Worker[] workers = new Worker[n];
        for (int i = 0; i < n; i++) {
            workers[i] = new Worker((double) wage[i] / quality[i], quality[i]);
        }
        Arrays.sort(workers, (a, b) -> Double.compare(a.ratio, b.ratio));
        
        double minCost = Double.MAX_VALUE;
        for (int i = k - 1; i < n; i++) {
            double currentRatio = workers[i].ratio;
            List<Integer> qualities = new ArrayList<>();
            for (int j = 0; j <= i; j++) {
                qualities.add(workers[j].quality);
            }
            Collections.sort(qualities);
            
            int sumQ = 0;
            for (int j = 0; j < k; j++) {
                sumQ += qualities.get(j);
            }
            minCost = Math.min(minCost, sumQ * currentRatio);
        }
        return minCost;
    }

    public static void main(String[] args) {
        int[] quality = {10, 20, 5}, wage = {70, 50, 30};
        System.out.println(mincostToHireWorkers(quality, wage, 2));
    }
}

Approach 2

Level II: Sort by Ratio + BST/TreeMap for Qualities

Intuition

As we iterate through workers sorted by ratio, we just need the $K$ smallest qualities we've seen so far. Instead of sorting all qualities at every step, we can maintain them in a sorted data structure (TreeMap in Java, multiset in C++, SortedList in Python). This reduces the cost of finding the sum of the $K$ smallest qualities to $O(K \log N)$ or better per step.

⏱ O(N^2) or O(N K log N) depending on the BST traversal for sum💾 O(N) to store the workers and the BST

Detailed Dry Run

quality = [10,20,5], wage = [70,50,30], k = 2 Ratios sorted: [(2.5,20), (6.0,5), (7.0,10)]

i=1 (ratio=6.0, q=5): BST = {5, 20}. Sum of 2 smallest = 25. Cost = 6.0 * 25 = 150.0.
i=2 (ratio=7.0, q=10): BST = {5, 10, 20}. Sum of 2 smallest = 15. Cost = 7.0 * 15 = 105.0.

java

import java.util.*;

public class Solution {
    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][0] = (double) wage[i] / quality[i];
            workers[i][1] = (double) quality[i];
        }
        Arrays.sort(workers, (a, b) -> Double.compare(a[0], b[0]));
        
        TreeMap<Integer, Integer> bst = new TreeMap<>();
        double minCost = Double.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            int q = (int) workers[i][1];
            bst.put(q, bst.getOrDefault(q, 0) + 1);
            
            if (i >= k - 1) {
                int sumQ = 0, count = 0;
                for (Map.Entry<Integer, Integer> entry : bst.entrySet()) {
                    int qVal = entry.getKey(), qCount = entry.getValue();
                    int take = Math.min(qCount, k - count);
                    sumQ += take * qVal;
                    count += take;
                    if (count == k) break;
                }
                minCost = Math.min(minCost, sumQ * workers[i][0]);
            }
        }
        return minCost;
    }
}

Approach 3

Level III: Max-Heap (Optimal)

Intuition

Why sort qualities again and again? We just need the K smallest qualities seen so far. As we iterate through the workers sorted by ratio, we can maintain a Max-Heap of size K. If we add a new quality and the heap size exceeds K, we pop the maximum quality out. This seamlessly keeps track of the sum of the K smallest qualities in O(log K) time per worker.

⏱ O(N log N) dominated by sorting the workers. Max-Heap operations take O(N log K)💾 O(N) to store the workers array, O(K) for the Max-Heap

Detailed Dry Run

quality = [10,20,5], wage = [70,50,30], k = 2 Workers sorted: [(2.5, q:20), (6.0, q:5), (7.0, q:10)] Wait, k=2. Max-Heap pq, quality_sum = 0

i=0, (2.5, 20): push 20. pq=[20], sum=20. size 1 < 2. Cost: ignore.
i=1, (6.0, 5): push 5. pq=[20,5], sum=25. size 2 == 2. Cost = 25 * 6.0 = 150.0. Min = 150.0
i=2, (7.0, 10): push 10. sum=35. pq=[20,10,5]. size 3 > 2 -> pop max (20). sum = 35 - 20 = 15. Size is now 2. Cost = 15 * 7.0 = 105.0. Min = min(150, 105) = 105.0. Return 105.0

java

import java.util.*;

public class Main {
    static class Worker {
        double ratio;
        int quality;
        public Worker(double r, int q) { ratio = r; quality = q; }
    }
    
    public static double mincostToHireWorkers(int[] quality, int[] wage, int k) {
        int n = quality.length;
        Worker[] workers = new Worker[n];
        for (int i = 0; i < n; i++) {
            workers[i] = new Worker((double) wage[i] / quality[i], quality[i]);
        }
        Arrays.sort(workers, (a, b) -> Double.compare(a.ratio, b.ratio));
        
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        double minCost = Double.MAX_VALUE;
        int qualitySum = 0;
        
        for (Worker worker : workers) {
            maxHeap.offer(worker.quality);
            qualitySum += worker.quality;
            
            if (maxHeap.size() > k) {
                qualitySum -= maxHeap.poll();
            }
            
            if (maxHeap.size() == k) {
                minCost = Math.min(minCost, qualitySum * worker.ratio);
            }
        }
        return minCost;
    }

    public static void main(String[] args) {
        int[] quality = {10, 20, 5}, wage = {70, 50, 30};
        System.out.println(mincostToHireWorkers(quality, wage, 2));
    }
}

← Previous QuestionTrapping Rain Water II

Next Question →IPO

Found an issue or have a suggestion?

Help us improve! Report bugs or suggest new features on our Telegram group.