Two integer arrays, quality and wage, describe n workers. Values at the same array index represent one worker's quality and minimum acceptable pay. Hire exactly k workers. Every hired worker must receive at least the corresponding minimum wage, and all hired workers must receive pay directly proportional to quality. Return the minimum possible total payment.
Example 1
Input: quality = [10, 20, 5], wage = [70, 50, 30], k = 2
Output: 105.00000
Explanation: Choose workers at indices 0 and 2. Their minimum wage-to-quality ratios are 70 / 10 = 7 and 30 / 5 = 6. To satisfy both workers while paying them at the same rate per quality unit, use the larger ratio 7. Therefore, their payments are 10 × 7 = 70 and 5 × 7 = 35, giving a total cost of 70 + 35 = 105, which is the minimum possible cost.
Example 2
Input: quality = [5], wage = [12], k = 1
Output: 12.00000
Explanation: A single selected worker receives the minimum wage of 12, so the smallest valid total equals 12.
Brute Force Approach
A small input allows every group of k workers to be examined. For one chosen group, proportional pay forces one shared rate. The largest wage-to-quality ratio inside the group is the smallest legal rate, because every smaller rate misses at least one wage demand.
Recursive selection offers two choices at each worker index: include the current worker or skip the current worker. Every search path carries the selected count, quality sum, and largest ratio. A complete group produces one legal total cost.
Algorithm
Begin at worker index
0with no selected workers, zero total quality, and a shared pay rate of zero, so the recursive state represents an empty group.Include the current worker in one branch and update both the quality sum and largest wage-to-quality ratio, because a legal group must cover every selected wage demand.
Skip the current worker in a second branch while preserving the current group values, so every possible subset remains reachable.
Evaluate a branch immediately after
kworkers are selected, because the largest stored ratio multiplied by the stored quality sum gives the group cost.Stop a branch after the remaining workers become fewer than the remaining positions, because no complete group can be formed along such a path.
Compare every complete group cost with the current minimum, so the best valid group survives after exhaustive exploration.
Return the stored minimum because exhaustive exploration compares every valid worker group.
Dry Run
minimum-cost-to-hire-k-workers-brute-force
Solution
#include <bits/stdc++.h>using namespace std;class Solution {private: double minimumCost; // Explores every group of exactly k workers void chooseWorkers(int index, int selected, int k, vector<int>& quality, vector<int>& wage, double maxRatio, int qualitySum) { // A complete group can update the minimum cost if (selected == k) { // The largest ratio sets the legal group rate double currentCost = maxRatio * qualitySum; // The smaller complete-group cost must survive minimumCost = min(minimumCost, currentCost); return; } int workerCount = quality.size(); int remainingNeeded = k - selected; int remainingWorkers = workerCount - index; // Too few remaining workers cannot fill the group if (remainingWorkers < remainingNeeded) { return; } // The current worker adds a new required rate double workerRatio = (double) wage[index] / quality[index]; double nextRatio = max(maxRatio, workerRatio); int nextQualitySum = qualitySum + quality[index]; // The include branch grows the selected group chooseWorkers(index + 1, selected + 1, k, quality, wage, nextRatio, nextQualitySum); // The skip branch preserves the selected group chooseWorkers(index + 1, selected, k, quality, wage, maxRatio, qualitySum); }public: // Finds the minimum cost by checking every group double mincostToHireWorkers(vector<int>& quality, vector<int>& wage, int k) { // Infinity allows the first group to set the answer minimumCost = numeric_limits<double>::infinity(); // The empty group starts before the first worker chooseWorkers(0, 0, k, quality, wage, 0.0, 0); return minimumCost; }};// Driver codeint main() { vector<int> quality = {10, 20, 5}; vector<int> wage = {70, 50, 30}; int k = 2; Solution obj; cout << fixed << setprecision(5) << obj.mincostToHireWorkers(quality, wage, k); return 0;}Note: Direct recursion may fail for large input values. Repeated subproblems create exponential work, so an online judge may report Time Limit Exceeded.
Complexity Analysis
Time Complexity: O(2N), where N is the number of workers, because each worker creates two choices in the worst case: include or skip.
Space Complexity: O(N), because the recursive call stack can contain at most one frame for each worker.
Optimal Approach
The exhaustive search repeats the same payment calculation across many groups. A fixed group always pays at the largest wage-to-quality ratio among selected workers. After workers are sorted by ratio, every processed worker has a ratio no larger than the current ratio and can legally receive pay at the current rate.
For a fixed current rate, a smaller quality sum always creates a smaller total cost. A max-heap keeps the k smallest qualities seen during the sorted sweep. Whenever the heap grows beyond k, removing the largest quality leaves the cheapest quality sum available under the current rate.
Algorithm
Build a pair of wage-to-quality ratio and quality for every worker, because the ratio gives the minimum pay required per quality unit.
Sort all worker pairs by increasing ratio, so every processed worker remains eligible under the current shared pay rate.
Keep a max-heap of selected qualities and a running quality sum, because the largest quality must be removed whenever the candidate group becomes too large.
Add each processed quality to both the heap and running sum, so the current worker joins the eligible candidate pool.
Remove the largest heap value after the heap size exceeds
k, because the remainingkqualities produce the smallest available quality sum.Multiply the current ratio by the quality sum whenever the heap contains
kvalues, because the product forms a legal total payment for a complete group.Return the smallest candidate cost found during the sweep, so every possible highest group ratio receives consideration.
Dry Run
minimum-cost-to-hire-k-workers-optimal-approach.png
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Finds the minimum cost with sorting and a heap double mincostToHireWorkers(vector<int>& quality, vector<int>& wage, int k) { int workerCount = quality.size(); vector<pair<double, int>> workers; // Every worker receives a ratio-quality pair for (int index = 0; index < workerCount; index++) { double ratio = (double) wage[index] / quality[index]; workers.push_back({ratio, quality[index]}); } // Increasing ratios reveal each possible group rate sort(workers.begin(), workers.end()); priority_queue<int> maxHeap; int qualitySum = 0; double minimumCost = numeric_limits<double>::infinity(); // The sweep grows the eligible worker pool for (auto worker : workers) { double ratio = worker.first; int workerQuality = worker.second; // The current worker joins the candidate group maxHeap.push(workerQuality); qualitySum += workerQuality; // Extra capacity must discard the largest quality if ((int) maxHeap.size() > k) { qualitySum -= maxHeap.top(); maxHeap.pop(); } // A full heap forms a legal group of size k if ((int) maxHeap.size() == k) { // The current ratio prices the full group double currentCost = ratio * qualitySum; // The smallest legal cost must survive minimumCost = min(minimumCost, currentCost); } } return minimumCost; }};// Driver codeint main() { vector<int> quality = {10, 20, 5}; vector<int> wage = {70, 50, 30}; int k = 2; Solution obj; cout << fixed << setprecision(5) << obj.mincostToHireWorkers(quality, wage, k); return 0;}Complexity Analysis
Time Complexity: O(N log N + N log k), where N is the number of workers. Sorting the workers takes O(N log N), and each heap update takes O(log k).
Space Complexity: O(N + k), because the sorted worker list stores N pairs and the max-heap stores at most k quality values.
Interview follow-up Questions
Yes. Wage-to-quality ratios and valid total payments can contain fractional values, so integer division can change sorting order and produce an incorrect minimum.
Be the first to add a comment.