857. Minimum Cost to Hire K Workers


Problem Description

In this problem, you are responsible for hiring a group of n workers. Each worker has two associated parameters: quality and wage. The quality of a worker represents a numerical value for the worker's skill level, while the wage indicates the minimum salary that the worker expects.

To form a paid group, exactly k workers need to be hired under two constraints:

  1. The payment of each worker must be proportional to their quality relative to the other workers in the group. This means if one worker has twice the quality compared with another worker in the group, they should also be paid twice as much.

  2. No worker can be paid less than their minimum wage expectation.

The goal is to calculate the minimum amount of money required to hire exactly k workers such that both of the aforementioned conditions are satisfied.

Intuition

The solution involves the concept of 'efficiency', which in this context is defined as the ratio of wage to quality for each worker. The intuition is to first sort the workers by their efficiency. This allows us to consider the workers in order of how much wage they require per unit quality.

Once sorted, the algorithm uses a min-heap to keep track of the k workers with the largest qualities, since any payment must be at least as large as the k-th worker's quality times the efficiency. By iterating through the sorted workers and maintaining the sum of the largest k qualities, when the k-th worker is added to the heap, the smallest ratio that satisfies all the workers' minimum wage expectations can be calculated. This is done by multiplying the total sum of the chosen qualities by the current worker's efficiency.

During iteration, the algorithm keeps updating the answer to record the least amount of money needed to form a paid group. This is achieved by maintaining a total quality sum and updating it as the group changes. When a new worker is added and the group exceeds k workers, the worker with the highest quality (and therefore the one contributing most to the total wage) is removed from the heap and the total quality sum. This step ensures that the maintained group always has k workers. The answer is updated whenever a potentially lower total wage for the group is found.

The use of a heap allows efficient removal of the worker with the highest quality in O(log k) time and helps to maintain the total quality sum and minimum possible wage for the group at each step.

Learn more about Greedy, Sorting and Heap (Priority Queue) patterns.

Solution Approach

The implementation of the solution provided in Python involves a sorting step and the use of a min-heap. The overall approach follows an efficient algorithm to minimize the total wage based on the ratio of wage to quality defined as efficiency. Here's a step-by-step explanation of how the solution works:

  1. Sorting: We start by computing the efficiency for each worker, which is the ratio of wage[i] to quality[i]. Then, we sort the workers based on this efficiency in ascending order. This ensures that we consider workers in increasing order of how much they expect to be paid relative to their quality.

  2. Initializing the Heap: We use a min-heap (in Python, a min-heap can be utilized by pushing negative values into it) to keep track of the k largest qualities encountered thus far in the sorted array. A heap is advantageous here because it allows us to efficiently retrieve and remove the worker with the highest quality, which in turn affects the total payment calculation.

  3. Iterative Calculation: Next, we iterate through the sorted workers and do the following:

    • Add the current worker's quality to the total quality sum (tot).
    • Push the negative of the current worker's quality to the heap to maintain the k largest qualities.
    • If the heap size exceeds k, it means we have more than k workers in the current group, so we pop from the heap (which removes the worker with the highest quality from our consideration) and reduce our total quality sum accordingly.
    • If the heap size is exactly k, we calculate the current cost to hire k workers based on the worker with the current efficiency and update the answer with the minimum cost observed so far. This is done by ans = min(ans, w / q * tot), where w / q represents the efficiency of the last worker added to meet the group size of k.
  4. Returning the Result: After going through all workers, the variable ans stores the minimum amount of money needed to hire k workers while satisfying the constraints. We return ans as the solution to the problem.

The key patterns used in this solution include sorting based on a custom comparator (efficiency), and utilizing a heap for dynamic subset selection - in this case, maintaining a subset of workers of size k with the greatest quality.

Algorithm Complexity: The time complexity of this algorithm is mainly governed by the sorting step, which is O(n log n), where n is the number of workers. Operating on the heap takes O(log k) time for each insertion and deletion, and since we go through the workers once, the overall complexity for heap operations is O(n log k). Hence, the total time complexity is O(n log n + n log k). The space complexity is O(n) to store the sorted efficiencies and the heap.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through the solution with a small example.

Suppose we have 4 workers, each with the following quality and wage expectations:

Workers:    1   2   3   4
Quality:    10  20  15  30
Wage:       60  120 90  180

We want to hire k = 2 workers while meeting the conditions specified in the problem.

Step 1: Sorting First, we calculate the efficiency wage[i] / quality[i] for each worker:

Efficiency: 6   6   6   6

Notice that in this case, all workers have the same efficiency, meaning any order keeps them sorted by efficiency. However, this won't always be the case.

Step 2: Initializing the Heap Now we initialize a min-heap to keep track of the largest qualities as we iterate through the workers. Initially, the heap is empty.

Step 3: Iterative Calculation We iterate through the sorted workers, keeping track of the total quality (tot) and potential total wage (ans).

  • For worker 1, quality = 10. We add it to tot and push -10 to the heap.
  • For worker 2, quality = 20. We add it to tot, giving us tot = 30, and push -20 to the heap.
  • The heap size is now equal to k, so we calculate the total payment for these k workers using the current efficiency, which is 6 * tot = 180. We set ans = 180.

To consider other possible combinations since the heap size now exceeds k, we must pop from the heap:

  • Since the heap is a min-heap with negatives, when we pop, we're removing the worker with the highest quality, in this case -10 (worker 1), leaving the heap with -20 and tot = 20.
  • We then move to worker 3, with quality = 15. Adding to tot gives us 35, and we push -15 to the heap.
  • The heap size again exceeds k, so we pop the largest quality, which is now -20 (worker 2), and tot becomes 15 (as we keep worker 3 and the new worker 4 in our consideration).
  • We must update ans if it gets lower. Worker 4 gets added with an efficiency of 6 and quality = 30. The new tot is 45, and ans becomes min(180, 6 * 45) = 270.

We proceed like this until all workers have been considered.

Step 4: Returning the Result After evaluating all possible groupings of k workers, we find that the minimum total payment we can get away with to hire k = 2 workers while meeting the constraints is ans = 180.

This is a very simplified example for clarity, where efficiencies were all equal. In practice, efficiencies would vary, and the sorting step would play a critical role in determining which workers could potentially be hired together within budget constraints.

Solution Implementation

1import heapq
2from typing import List
3
4class Solution:
5    def mincostToHireWorkers(
6        self, quality: List[int], wage: List[int], k: int
7    ) -> float:
8        # Pair each worker's quality with their minimum wage 
9        # and sort the workers based on their wage-to-quality ratio.
10        workers = sorted(zip(quality, wage), key=lambda x: x[1] / x[0])
11      
12        # Initialize the answer as infinity to be later minimized
13        # Initialize the total quality of workers hired so far as zero
14        min_cost = float('inf')
15        total_quality = 0
16      
17        # Max heap to store the negative of qualities, 
18        # since heapq in Python is a min heap by default
19        max_heap = []
20      
21        # Iterate over each worker
22        for q, w in workers:
23            # Add the current worker's quality to the total quality
24            total_quality += q
25            # Push the negative quality to the heap
26            heapq.heappush(max_heap, -q)
27          
28            # If we have more than k workers, remove the one with the highest quality
29            if len(max_heap) > k:
30                # Since we stored negative qualities, popping from heap retrieves
31                # and removes the biggest quality from the total
32                total_quality += heapq.heappop(max_heap)
33          
34            # If we've collected a group of k workers
35            if len(max_heap) == k:
36                # Calculate the current cost for this group of workers, which is
37                # the wage-to-quality ratio of the current worker times total quality
38                # and update the minimum cost if it's less than the previous minimum
39                min_cost = min(min_cost, w / q * total_quality)
40      
41        # Return the minimum cost found to hire k workers
42        return min_cost
43
44# Example usage:
45# sol = Solution()
46# result = sol.mincostToHireWorkers([10, 20, 5], [70, 50, 30], 2)
47# print(result)  # Should print the minimum cost to hire 2 workers
48
1import java.util.Arrays;
2import java.util.PriorityQueue;
3
4class Solution {
5  
6    // This class represents workers with their quality and wage ratio
7    class Worker {
8        double wageQualityRatio;
9        int quality;
10      
11        Worker(int quality, int wage) {
12            this.quality = quality;
13            this.wageQualityRatio = (double) wage / quality;
14        }
15    }
16  
17    public double mincostToHireWorkers(int[] quality, int[] wage, int k) {
18        int numWorkers = quality.length;
19        Worker[] workers = new Worker[numWorkers];
20      
21        // Create Worker instances combining both quality and wage.
22        for (int i = 0; i < numWorkers; ++i) {
23            workers[i] = new Worker(quality[i], wage[i]);
24        }
25      
26        // Sort the workers based on their wage-to-quality ratio.
27        Arrays.sort(workers, (a, b) -> Double.compare(a.wageQualityRatio, b.wageQualityRatio));
28      
29        // Use a max heap to keep track of the highest quality workers.
30        PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);
31        double minCost = Double.MAX_VALUE; // Initialize minimum cost to a large number.
32        int totalQuality = 0; // Tracks the total quality of hired workers.
33      
34        // Iterate through the sorted workers by increasing wage-to-quality ratio.
35        for (Worker worker : workers) {
36            // Add the current worker's quality to the total.
37            totalQuality += worker.quality;
38            // Add the current worker's quality to the max heap.
39            maxHeap.offer(worker.quality);
40          
41            // If we have enough workers (exactly k), we can try to form an answer.
42            if (maxHeap.size() == k) {
43                // Calculate the cost based on current worker's wage-to-quality ratio.
44                minCost = Math.min(minCost, totalQuality * worker.wageQualityRatio);
45                // Remove the worker with the highest quality (to maintain only k workers).
46                totalQuality -= maxHeap.poll();
47            }
48        }
49      
50        return minCost; // Return the minimum cost found.
51    }
52}
53
1#include <vector>
2#include <queue>
3#include <algorithm>
4
5using namespace std;
6
7class Solution {
8public:
9    // Method that returns the minimum cost to hire k workers based on their quality and the minimum wage they will work for.
10    double mincostToHireWorkers(vector<int>& quality, vector<int>& wage, int k) {
11        int numWorkers = quality.size();
12        vector<pair<double, int>> workerRatios(numWorkers); // This will contain wage/quality ratio and quality.
13      
14        // Generate wage to quality ratios for all workers and store them with the quality.
15        for (int i = 0; i < numWorkers; ++i) {
16            workerRatios[i] = {(double) wage[i] / quality[i], quality[i]};
17        }
18      
19        // Sort the workers based on their wage/quality ratio. Lower ratio means more cost-effective.
20        sort(workerRatios.begin(), workerRatios.end());
21      
22        priority_queue<int> qualityMaxHeap; // Max heap to maintain the top k largest qualities.
23        double minCost = 1e9; // Initialize minimum cost with an high value.
24        int totalQuality = 0; // Total quality of the hired workers.
25      
26        // Loop through the sorted worker ratios
27        for (auto& [ratio, workerQuality] : workerRatios) {
28            totalQuality += workerQuality; // Add current worker's quality to the total quality.
29            qualityMaxHeap.push(workerQuality); // Add current worker's quality to max heap.
30          
31            // Once we have a group of k workers.
32            if (qualityMaxHeap.size() == k) {
33                // Calculate the cost of hiring the current group and update minimum cost if necessary.
34                minCost = min(minCost, totalQuality * ratio);
35                // Remove the worker with the highest quality as we want to try for a more cost-effective group next.
36                totalQuality -= qualityMaxHeap.top();
37                qualityMaxHeap.pop();
38            }
39        }
40        // Return the minimum cost found for hiring k workers.
41        return minCost;
42    }
43};
44
1function minCostToHireWorkers(quality: Array<number>, wage: Array<number>, k: number): number {
2    let numWorkers = quality.length;
3    let workerRatios: Array<{ ratio: number; workerQuality: number }> = [];
4
5    // Generate wage to quality ratio for all workers and store them along with the quality.
6    for (let i = 0; i < numWorkers; ++i) {
7        workerRatios.push({ ratio: wage[i] / quality[i], workerQuality: quality[i] });
8    }
9  
10    // Sort the workers based on their wage to quality ratio. Lower ratio means more cost-effective.
11    workerRatios.sort((a, b) => a.ratio - b.ratio);
12  
13    let qualityMaxHeap: Array<number> = []; // Using array as max heap.
14    let minCost: number = Number.MAX_VALUE; // Initialize minimum cost to the highest possible value.
15    let totalQuality: number = 0; // Total quality of the hired workers.
16  
17    workerRatios.forEach(worker => {
18        totalQuality += worker.workerQuality; // Add current worker's quality to total
19        qualityMaxHeap.push(worker.workerQuality);
20      
21        // Maintain the max heap property by sorting only the k highest qualities.
22        if (qualityMaxHeap.length > k) {
23            qualityMaxHeap.sort((a, b) => b - a); // Sort to get the highest quality on top
24            totalQuality -= qualityMaxHeap[0]; // Remove the highest quality
25            qualityMaxHeap.shift(); // Remove the first element from array
26        }
27      
28        // Once we have exactly k workers, calculate the cost of hiring the group
29        if (qualityMaxHeap.length === k) {
30            minCost = Math.min(minCost, totalQuality * worker.ratio);
31        }
32    });
33
34    // Return the minimum cost found for hiring k workers.
35    return minCost;
36}
37

Time and Space Complexity

Time Complexity

The time complexity of the code consists of several components:

  1. Sorting: The list t is sorted based on the ratio of wage to quality using Python's built-in sort function, which has a time complexity of O(n log n) where n is the number of workers.

  2. Heap Operations: For each worker in the sorted list, the algorithm performs heap push (heappush) and possibly heap pop (heappop) operations when the heap size is equal to k. Pushing onto the heap has a time complexity of O(log k) and popping from the heap also has a complexity of O(log k).

Given there are n workers, and therefore n heappush operations, and at most n heappop operations when the heap size reaches k, the heap operations give us a total time complexity of O(n log k).

So, the overall time complexity is the sum of the sorting complexity and the heap operations complexity: O(n log n + n log k).

Space Complexity

The space complexity is determined by the extra space used by the heap and the sorted list:

  1. Sorted List: The sorted list t takes O(n) space since it contains a tuple for each worker.

  2. Heap: The heap h can store up to k elements, so it has a space complexity of O(k).

Therefore, the total space complexity is the sum of the space complexities for the sorted list and the heap, which is O(n + k).

Learn more about how to find time and space complexity quickly using problem constraints.


Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

Which of these properties could exist for a graph but not a tree?


Recommended Readings

Want a Structured Path to Master System Design Too? Donā€™t Miss This!


Load More