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:
-
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.
-
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:
-
Sorting: We start by computing the efficiency for each worker, which is the ratio of
wage[i]
toquality[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. -
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. -
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 thank
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 hirek
workers based on the worker with the current efficiency and update the answer with the minimum cost observed so far. This is done byans = min(ans, w / q * tot)
, wherew / q
represents the efficiency of the last worker added to meet the group size ofk
.
- Add the current worker's quality to the total quality sum (
-
Returning the Result: After going through all workers, the variable
ans
stores the minimum amount of money needed to hirek
workers while satisfying the constraints. We returnans
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 EvaluatorExample 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 totot
and push-10
to the heap. - For worker 2,
quality = 20
. We add it totot
, giving ustot = 30
, and push-20
to the heap. - The heap size is now equal to
k
, so we calculate the total payment for thesek
workers using the current efficiency, which is6 * tot = 180
. We setans = 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
andtot = 20
. - We then move to worker 3, with
quality = 15
. Adding totot
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), andtot
becomes15
(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 of6
andquality = 30
. The newtot
is45
, andans
becomesmin(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:
-
Sorting: The list
t
is sorted based on the ratio ofwage
toquality
using Python's built-in sort function, which has a time complexity ofO(n log n)
wheren
is the number of workers. -
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 tok
. Pushing onto the heap has a time complexity ofO(log k)
and popping from the heap also has a complexity ofO(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:
-
Sorted List: The sorted list
t
takesO(n)
space since it contains a tuple for each worker. -
Heap: The heap
h
can store up tok
elements, so it has a space complexity ofO(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.
Which of these properties could exist for a graph but not a tree?
Recommended Readings
Greedy Introduction div class responsive iframe iframe src https www youtube com embed WTslqPbj7I title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe div When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you to calculate the max min of some value Commonly you may see this phrased in the problem as max min longest shortest largest smallest etc These keywords can be identified by just scanning
Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced
https algomonster s3 us east 2 amazonaws com cover_photos heap svg Priority Queue and Heap What is the relationship between priority queue and heap Priority Queue is an Abstract Data Type and Heap is the concrete data structure we use to implement a priority queue Priority Queue A priority queue
Want a Structured Path to Master System Design Too? Donāt Miss This!