Minimum Cost to Hire K Workers
HardPrompt
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 must be paid at least their minimum wage expectation.
- In the group, each worker's pay must be directly proportional to their quality. This means if a worker’s quality is double that of another worker in the group, then they must be paid twice as much as the other worker.
Given the integer k, return the least amount of money needed to form a paid group satisfying the above conditions. Answers within 10-5 of the actual answer will be accepted.
Example 1:
Input: quality = [10,20,5], wage = [70,50,30], k = 2
Output: 105.00000
Explanation: We pay 70 to 0th worker and 35 to 2nd worker.Example 2:
Input: quality = [3,1,10,10,1], wage = [4,8,2,2,7], k = 3
Output: 30.66667
Explanation: We pay 4 to 0th worker, 13.33333 to 2nd and 3rd workers separately.
Constraints:
n == quality.length == wage.length1 <= k <= n <= 1041 <= quality[i], wage[i] <= 104
Approaches
3 approaches with complexity analysis and trade-offs.
The most straightforward approach is to exhaustively check every possible group of k workers. We can generate all combinations of k workers from the total pool of n workers. For each of these groups, we calculate the minimum cost required to hire them according to the rules and keep track of the overall minimum cost found.
Algorithm
- Initialize
min_costto a very large number. - Generate all combinations of
kworkers from thenavailable workers. This can be done using a recursive backtracking function. - For each combination (a group of
kworkers):- Calculate the group's ratio
R. This must be the maximum ofwage[i] / quality[i]for all workersiin the group to satisfy everyone's minimum wage. - Calculate the sum of qualities,
S, for all workers in the group. - The cost for this group is
C = R * S. - Update
min_cost = min(min_cost, C).
- Calculate the group's ratio
- After checking all combinations,
min_costwill hold the result.
Walkthrough
For any given group of k workers, the payment structure must be fair and meet minimum expectations. The rule that pay is proportional to quality implies paid_wage[i] = ratio * quality[i] for some constant ratio. To meet the minimum wage wage[i], we must have ratio * quality[i] >= wage[i], which means ratio >= wage[i] / quality[i]. This must hold for all workers in the group. To minimize the total cost, which is ratio * sum(qualities), we should choose the smallest possible ratio. Therefore, for a given group, ratio = max(wage[i] / quality[i]) over all workers i in that group.
The brute-force algorithm iterates through every unique subset of k workers. For each subset, it computes this maximum ratio, sums up the qualities, calculates the total cost, and updates a global minimum. This process guarantees finding the optimal solution since it explores the entire search space.
class Solution { double minCost = Double.MAX_VALUE; public double mincostToHireWorkers(int[] quality, int[] wage, int k) { int n = quality.length; findCombinations(0, new ArrayList<>(), quality, wage, k); return minCost; } private void findCombinations(int start, List<Integer> combination, int[] quality, int[] wage, int k) { if (combination.size() == k) { calculateCost(combination, quality, wage); return; } if (start >= quality.length) { return; } // Using a loop to generate combinations and avoid deep recursion for the same path for (int i = start; i < quality.length; i++) { combination.add(i); findCombinations(i + 1, combination, quality, wage, k); combination.remove(combination.size() - 1); // backtrack } } private void calculateCost(List<Integer> combination, int[] quality, int[] wage) { double maxRatio = 0.0; int sumQuality = 0; for (int i : combination) { maxRatio = Math.max(maxRatio, (double) wage[i] / quality[i]); sumQuality += quality[i]; } minCost = Math.min(minCost, maxRatio * sumQuality); }}Complexity
Time
O(C(n, k) * k) - Where C(n, k) is the number of combinations, `n! / (k! * (n-k)!)`. This is exponential and grows extremely fast, making it impractical for the given constraints.
Space
O(k) - This is for storing the current combination and for the recursion stack depth.
Trade-offs
Pros
Conceptually simple and easy to understand.
Guaranteed to find the correct answer.
Cons
Extremely inefficient due to the combinatorial explosion of possible groups.
Will result in a 'Time Limit Exceeded' error for all but the smallest input sizes.
This approach is an improvement over the pure brute-force method. Instead of generating combinations, it iterates through each worker and considers them as the one who sets the wage-to-quality ratio for the group. This worker is called the 'captain'. The captain's ratio is the highest ratio in the group, and all other members must have a ratio less than or equal to the captain's.
Algorithm
- Initialize
min_costto a very large number. - Iterate through each worker
ifrom0ton-1, considering them as the 'captain' of the group. - For each potential captain
i, the group's payment ratio is fixed atcaptain_ratio = (double)wage[i] / quality[i]. - Create a list of
eligible_qualitiesfor all workersjwhose ratio(double)wage[j] / quality[j]is less than or equal tocaptain_ratio. - If the number of eligible workers is less than
k, we cannot form a valid group, so we continue to the next captain. - If there are enough eligible workers, sort the
eligible_qualitieslist. - To minimize cost, pick the
ksmallest qualities from the sorted list and sum them up (sum_quality). - Calculate the cost for this group:
current_cost = captain_ratio * sum_quality. - Update
min_cost = min(min_cost, current_cost). - Return
min_costafter checking all possible captains.
Walkthrough
The logic hinges on the fact that for any optimal group of k workers, the group's wage-to-quality ratio will be determined by one of its members—the one with the highest wage/quality ratio. So, we can iterate through every worker, i, and hypothesize that they are this 'captain'.
For each potential captain i, we fix the group's ratio to R_i = wage[i] / quality[i]. Then, we find all other workers j who could be part of this group. A worker j is eligible if their own ratio wage[j] / quality[j] is not greater than R_i. From this pool of eligible workers (which includes the captain i), we must choose k workers. To minimize the total cost R_i * sum(qualities), we must select the k eligible workers with the lowest qualities.
We gather the qualities of all eligible workers, sort them, and take the sum of the smallest k qualities. This sum is then multiplied by R_i to get a potential minimum cost. We repeat this for all n possible captains and take the minimum of all calculated costs.
import java.util.ArrayList; import java.util.Collections;import java.util.List; class Solution { public double mincostToHireWorkers(int[] quality, int[] wage, int k) { int n = quality.length; double minCost = Double.MAX_VALUE; for (int i = 0; i < n; i++) { double captainRatio = (double) wage[i] / quality[i]; List<Integer> eligibleQualities = new ArrayList<>(); for (int j = 0; j < n; j++) { if ((double) wage[j] / quality[j] <= captainRatio) { eligibleQualities.add(quality[j]); } } if (eligibleQualities.size() < k) { continue; } Collections.sort(eligibleQualities); int qualitySum = 0; for (int l = 0; l < k; l++) { qualitySum += eligibleQualities.get(l); } minCost = Math.min(minCost, captainRatio * qualitySum); } return minCost; }}Complexity
Time
O(N^2 * log N) - The outer loop runs N times. Inside, we iterate N times to find eligible workers (O(N)) and then sort a list of up to N elements (O(N log N)). This makes the total complexity O(N * (N + N log N)) which simplifies to O(N^2 log N).
Space
O(N) - To store the list of qualities for eligible workers, which can be up to N in the worst case.
Trade-offs
Pros
More efficient than the combinatorial brute-force approach.
Reduces the problem from exponential to polynomial time.
Cons
The time complexity of O(N^2 log N) is still too high for the given constraints (N up to 10^4).
Involves redundant computations, as for each captain, we rebuild and re-sort a list of eligible workers.
The most efficient solution uses a greedy approach combined with a max-heap. The key idea is to process workers in increasing order of their wage-to-quality ratio. By doing this, whenever we consider a worker i, they have the highest ratio among all workers processed so far. This worker can act as the 'captain' for a group formed from the workers seen up to this point. We use a max-heap to efficiently maintain a group of k workers with the smallest sum of qualities.
Algorithm
- Create a custom
Workerclass or object to store each worker's quality and their wage-to-quality ratio. - Create a list of these
Workerobjects for allnworkers. - Sort this list of workers in ascending order based on their ratio.
- Initialize
minCostto infinity,qualitySumto 0, and a max-heap (aPriorityQueuein Java with a reverse order comparator). - Iterate through the ratio-sorted list of workers:
- Add the current worker's quality to
qualitySumand push it onto the max-heap. - If the heap's size becomes greater than
k, it means we have more thankworkers in our potential group. To keep only thekworkers with the smallest qualities, we remove the largest quality from the heap (usingpoll()) and subtract it fromqualitySum. - If the heap's size is exactly
k, we have a valid group. The members of this group are the ones whose qualities are currently in the heap. The group's ratio is determined by the current worker (who has the highest ratio among all workers processed so far). - Calculate the cost for this group:
cost = current_worker.ratio * qualitySum. - Update
minCost = min(minCost, cost).
- Add the current worker's quality to
- After the loop finishes,
minCostwill hold the minimum cost.
Walkthrough
First, we encapsulate each worker's data (quality, wage, and the calculated ratio = wage/quality) into an object. We then sort all workers based on their ratio in ascending order.
We iterate through this sorted list. As we process each worker, we add their quality to a max-heap. The max-heap's purpose is to keep track of the k smallest qualities encountered so far. If, after adding a new quality, the heap's size exceeds k, we remove the largest element (the top of the max-heap). This ensures the heap always contains the k workers with the lowest qualities among those considered.
Whenever the heap contains exactly k workers, we have a valid potential group. The workers in this group are those whose qualities are in the heap. Because we are iterating through workers sorted by ratio, the current worker has the highest ratio among this group. Therefore, this worker's ratio can be used as the ratio for the entire group. We calculate the cost for this group by multiplying the current worker's ratio by the sum of qualities in the heap. We keep track of the minimum cost found across all such valid groups.
This approach works because for any set of k workers, the cost is max_ratio * sum_quality. By sorting by ratio, we ensure that when we calculate a cost, the current worker's ratio is indeed the max_ratio for the group of k smallest-quality workers considered so far. The heap allows us to maintain this sum_quality efficiently.
import java.util.ArrayList;import java.util.Collections;import java.util.List;import java.util.PriorityQueue; class Solution { class Worker implements Comparable<Worker> { public int quality; public double ratio; public Worker(int quality, int wage) { this.quality = quality; this.ratio = (double) wage / quality; } @Override public int compareTo(Worker other) { return Double.compare(this.ratio, other.ratio); } } public double mincostToHireWorkers(int[] quality, int[] wage, int k) { int n = quality.length; List<Worker> workers = new ArrayList<>(); for (int i = 0; i < n; i++) { workers.add(new Worker(quality[i], wage[i])); } Collections.sort(workers); double minCost = Double.MAX_VALUE; int qualitySum = 0; PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder()); for (Worker worker : workers) { qualitySum += worker.quality; maxHeap.offer(worker.quality); if (maxHeap.size() > k) { qualitySum -= maxHeap.poll(); } if (maxHeap.size() == k) { minCost = Math.min(minCost, worker.ratio * qualitySum); } } return minCost; }}Complexity
Time
O(N log N) - Sorting the N workers takes O(N log N). The subsequent loop iterates N times, with each heap operation (offer/poll) taking O(log k) time. The total time for the loop is O(N log k). Therefore, the overall time complexity is O(N log N + N log k), which is dominated by the sorting step, resulting in O(N log N).
Space
O(N) - We need O(N) space to store the list of worker objects. The max-heap requires O(k) space. Thus, the total space complexity is O(N + k) = O(N).
Trade-offs
Pros
Optimal and highly efficient, passing all test cases within the time limit.
Cleverly combines sorting and a priority queue to avoid re-computation.
Cons
The logic is more complex and less intuitive than the brute-force methods.
Requires understanding of greedy algorithms and priority queues.
Solutions
Solution
class Solution {public double mincostToHireWorkers(int[] quality, int[] wage, int k) { int n = quality.length; Pair[] t = new Pair[n]; for (int i = 0; i < n; ++i) { t[i] = new Pair(quality[i], wage[i]); } Arrays.sort(t, (a, b)->Double.compare(a.x, b.x)); PriorityQueue<Integer> pq = new PriorityQueue<>((a, b)->b - a); double ans = 1 e9; int tot = 0; for (var e : t) { tot += e.q; pq.offer(e.q); if (pq.size() == k) { ans = Math.min(ans, tot * e.x); tot -= pq.poll(); } } return ans; }} class Pair { double x; int q; Pair(int q, int w) { this.q = q; this.x = (double)w / q; }}class Solution {public: double mincostToHireWorkers(vector<int> &quality, vector<int> &wage, int k) { int n = quality.size(); vector<pair<double, int>> t(n); for (int i = 0; i < n; ++i) { t[i] = {(double)wage[i] / quality[i], quality[i]}; } sort(t.begin(), t.end()); priority_queue<int> pq; double ans = 1e9; int tot = 0; for (auto &[x, q] : t) { tot += q; pq.push(q); if (pq.size() == k) { ans = min(ans, tot * x); tot -= pq.top(); pq.pop(); } } return ans; }};class Solution: def mincostToHireWorkers(self, quality: List[int], wage: List[int], k: int) -> float: t = sorted(zip(quality, wage), key=lambda x: x[1] / x[0]) ans, tot = inf, 0 h = [] for q, w in t: tot += q heappush(h, - q) if len(h) == k: ans = min(ans, w / q * tot) tot += heappop(h) return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.