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 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 = 3
Output: 30.66667
Explanation: 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.
Solution:
Let's read description first and figure out the two rules:
"1. Every worker in the paid group should be paid in the ratio of their quality compared to other workers in the paid group." So for any two workers in the paid group, we have wage[i] : wage[j] = quality[i] : quality[j] So we have wage[i] : quality[i] = wage[j] : quality[j] We pay wage to every worker in the group with the same ratio compared to his own quality.
"2. Every worker in the paid group must be paid at least their minimum wage expectation." For every worker, he has an expected ratio of wage compared to his quality.
So to minimize the total wage, we want a small ratio. So we sort all workers with their expected ratio, and pick up K first worker. Now we have a minimum possible ratio for K worker and we their total quality.
As we pick up next worker with bigger ratio, we increase the ratio for whole group. Meanwhile we remove a worker with highest quality so that we keep K workers in the group. We calculate the current ratio * total quality = total wage for this group.
We redo the process and we can find the minimum total wage. Because workers are sorted by ratio of wage/quality. For every ratio, we find the minimum possible total quality of K workers.
Why do we choose the highest quality person to remove? Why not choosing other workers?
Since the workers are sorted in the increasing order of the wage/quality ratio, the global ratio will never decrease. For the previously scanned workers, we do not care about their personal ratios any more because their personal ratios will always be less than (or equal to) the current global ratio. So the previous workers' personal ratio will never affect the total payment. Similarly, their personal base payment (i.e. the wage input) has been satisfied already. As the global ratio increases, their actual payment will only increase or stay the same, and will never become lower than their base payment. So when deciding whom to remove, the only thing that matters is the workers' quality. With a given global ratio, removing the highest quality worker will reduces the total payment as much as possible. That is why we want to removing the highest quality worker.
class Solution {
public double mincostToHireWorkers(int[] quality, int[] wage, int K) {
int n = wage.length;
double[][] workers = new double[n][2];
for (int i = 0; i < n; i ++) {
workers[i][0] = wage[i] * 1.0 / quality[i];
workers[i][1] = quality[i];
}
Arrays.sort(workers, (a, b) -> { return Double.compare(a[0], b[0]); });
PriorityQueue<Double> q = new PriorityQueue(Collections.reverseOrder());
double qSum = 0;
double result = Double.MAX_VALUE;
for (int i = 0; i < n; i ++) {
qSum += workers[i][1];
q.offer(workers[i][1]);
if (q.size() > K) {
qSum -= q.poll();
}
if (q.size() == K) {
result = Math.min(result, qSum * workers[i][0]);
}
}
return result;
}
}