Formatted question description: https://leetcode.ca/all/857.html
857. Minimum Cost to Hire K Workers (Hard)
There are N
workers. The i
th worker has a quality[i]
and a minimum wage expectation wage[i]
.
Now we want to hire exactly K
workers to form a paid group. When hiring 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.
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 2th 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 2th and 3th workers seperately.
Note:
1 <= K <= N <= 10000
, whereN = quality.length = wage.length
1 <= quality[i] <= 10000
1 <= wage[i] <= 10000
 Answers within
10^5
of the correct answer will be considered correct.
Related Topics:
Heap
TLE version. Greedy
Try person[i]
as the baseline. Use her W[i] / Q[i]
as the factor to get others’ wages. Drop those who can’t meet their min wages.
For the rest, sum the smallest K
wages.
// OJ: https://leetcode.com/problems/minimumcosttohirekworkers/
// Time: O(N^2 * logN)
// Space: O(N)
// Ref: https://leetcode.com/problems/minimumcosttohirekworkers/solution/
// NOTE: this solution will get TLE
class Solution {
public:
double mincostToHireWorkers(vector<int>& Q, vector<int>& W, int K) {
int N = Q.size();
double ans = DBL_MAX;
for (int i = 0; i < N; ++i) {
double factor = (double) W[i] / Q[i];
vector<double> costs;
for (int j = 0; j < N; ++j) {
double c = factor * Q[j];
if (c < W[j]) continue;
costs.push_back(c);
}
if (costs.size() < K) continue;
sort(costs.begin(), costs.end());
double sum = accumulate(costs.begin(), costs.begin() + K, 0.0);
ans = min(ans, sum);
}
return ans;
}
};
Solution 1. Max Heap
If we select person[i]
as the benchmark, W[i]/Q[i]
will be used as the rate
. All other people get Q[j] * rate
.
If Q[j] * rate[i]
is smaller than W[j]
, i.e. Q[j] * rate[i] < W[j]
, or rate[i] < rate[j]
, person[j]
can’t work.
So rate[i]
can only make the people with equal or smaller rates to be able to work.
 The greatest rate can make all people work, but results in greater total wage.
 The smaller rate can make less people work, but results in smaller total wage.
Hence we can iterate people in ascending order of rate.
We use a max heap pq
to keep the qualities of people, and sum
to track the sum of qualities of people in the pq
.
For person[i]
, we add her quality into the pq
. And pop if the pq
has more than K
people. We update the sum
accordingly.
If there are K
people in the pq
, then sum * rate[i]
is the total wage. We just need to find the minimal total wage.
// OJ: https://leetcode.com/problems/minimumcosttohirekworkers/
// Time: O(NlogN)
// Space: O(N)
class Solution {
public:
double mincostToHireWorkers(vector<int>& Q, vector<int>& W, int K) {
int N = Q.size(), sum = 0;
double ans = DBL_MAX;
vector<int> id(N);
vector<double> rate(N);
for (int i = 0; i < N; ++i) rate[i] = (double)W[i] / Q[i];
iota(begin(id), end(id), 0);
sort(begin(id), end(id), [&](int a, int b) { return rate[a] < rate[b]; });
priority_queue<int> pq;
for (int i = 0; i < N; ++i) {
sum += Q[id[i]];
pq.push(Q[id[i]]);
if (pq.size() > K) {
sum = pq.top();
pq.pop();
}
if (pq.size() == K) ans = min(ans, rate[id[i]] * sum);
}
return ans;
}
};
Java

class Solution { public double mincostToHireWorkers(int[] quality, int[] wage, int K) { int length = quality.length; int[][] qualityWageArray = new int[length][2]; for (int i = 0; i < length; i++) { qualityWageArray[i][0] = quality[i]; qualityWageArray[i][1] = wage[i]; } Arrays.sort(qualityWageArray, new Comparator<int[]>() { public int compare(int[] qualityWage1, int[] qualityWage2) { return qualityWage1[1] * qualityWage2[0]  qualityWage1[0] * qualityWage2[1]; } }); double ratio = 0; int totalQuality = 0; PriorityQueue<Integer> priorityQueue = new PriorityQueue<Integer>(new Comparator<Integer>() { public int compare(Integer num1, Integer num2) { return num2  num1; } }); for (int i = 0; i < K; i++) { int[] qualityWage = qualityWageArray[i]; int curQuality = qualityWage[0], curWage = qualityWage[1]; totalQuality += curQuality; priorityQueue.offer(curQuality); double curRatio = 1.0 * curWage / curQuality; ratio = Math.max(ratio, curRatio); } double minCost = totalQuality * ratio; for (int i = K; i < length; i++) { int prevQuality = priorityQueue.poll(); totalQuality = prevQuality; int[] qualityWage = qualityWageArray[i]; int curQuality = qualityWage[0], curWage = qualityWage[1]; totalQuality += curQuality; priorityQueue.offer(curQuality); double curRatio = 1.0 * curWage / curQuality; ratio = Math.max(ratio, curRatio); double curCost = totalQuality * ratio; minCost = Math.min(minCost, curCost); } return minCost; } }

// OJ: https://leetcode.com/problems/minimumcosttohirekworkers/ // Time: O(N^2 * logN) // Space: O(N) // Ref: https://leetcode.com/problems/minimumcosttohirekworkers/solution/ // NOTE: this solution will get TLE class Solution { public: double mincostToHireWorkers(vector<int>& Q, vector<int>& W, int K) { int N = Q.size(); double ans = DBL_MAX; for (int i = 0; i < N; ++i) { double factor = (double) W[i] / Q[i]; vector<double> costs; for (int j = 0; j < N; ++j) { double c = factor * Q[j]; if (c < W[j]) continue; costs.push_back(c); } if (costs.size() < K) continue; sort(costs.begin(), costs.end()); double sum = accumulate(costs.begin(), costs.begin() + K, 0.0); ans = min(ans, sum); } return ans; } };

class Solution(object): def mincostToHireWorkers(self, quality, wage, K): """ :type quality: List[int] :type wage: List[int] :type K: int :rtype: float """ works = sorted([(w / float(q), q) for w, q in zip(wage, quality)]) que = [] qsum = 0 res = float("inf") for rate, q in works: heapq.heappush(que, q) qsum += q if len(que) > K: qsum += heapq.heappop(que) if len(que) == K: res = min(res, qsum * rate) return res