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 = 2Output:105.00000Explanation: We pay 70 to 0-th worker and 35 to 2-th worker.

**Example 2:**

Input:quality = [3,1,10,10,1], wage = [4,8,2,2,7], K = 3Output:30.66667Explanation: We pay 4 to 0-th worker, 13.33333 to 2-th and 3-th workers seperately.

**Note:**

`1 <= K <= N <= 10000`

, where`N = 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/minimum-cost-to-hire-k-workers/
// Time: O(N^2 * logN)
// Space: O(N)
// Ref: https://leetcode.com/problems/minimum-cost-to-hire-k-workers/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/minimum-cost-to-hire-k-workers/
// 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;
}
}
```