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:
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.length1 <= quality[i] <= 100001 <= wage[i] <= 1000010^-5 of the correct answer will be considered correct.
Approach #1: C++.
class Solution {
public:
double mincostToHireWorkers(vector<int>& quality, vector<int>& wage, int K) {
vector<vector<double>> workers;
for (int i = 0; i < wage.size(); ++i)
workers.push_back({(double)wage[i]/quality[i], (double)quality[i]});
sort(workers.begin(), workers.end());
double res = INT_MAX, qsum = 0;
priority_queue<int> pq;
for (auto worker : workers) {
qsum += worker[1];
pq.push(worker[1]);
if (pq.size() > K) qsum -= pq.top(), pq.pop();
if (pq.size() == K) res = min(res, qsum*worker[0]);
}
return res;
}
};
In this solution we use a vector to store the ratio of wage/quality and the quality, then sort the vector with ratio.
We travel the vector when the priority_queue‘s size < k we add the quality to the qsum.
When priority_queue‘s size == K we calculate the total wages at this status.
Last we select the minimum total wages as the result.
O(NlogN) for sort.O(NlogK) for priority queue.
Approach #2: Java. [Greedy]
class Solution {
public double mincostToHireWorkers(int[] quality, int[] wage, int K) {
int N = quality.length;
double ans = 1e9;
for (int captain = 0; captain < N; ++captain) {
double factor = (double)wage[captain] / quality[captain];
double prices[] = new double[N];
int t = 0;
for (int worker = 0; worker < N; ++worker) {
double price = factor * quality[worker];
if (price < wage[worker]) continue;
prices[t++] = price;
}
if (t < K) continue;
Arrays.sort(prices, 0, t);
double cand = 0;
for (int i = 0; i < K; ++i)
cand += prices[i];
ans = Math.min(ans, cand);
}
return ans;
}
}
Having the similar thinking with above code, but this solution don‘t use heap to maintain the ratio, so the time complex is bigger than above.
O(N^2 \log N)O(N2logN), where NN is the number of workers.
857. Minimum Cost to Hire K Workers
原文：https://www.cnblogs.com/ruruozhenhao/p/10171375.html