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, whereN = quality.length = wage.length1 <= quality[i] <= 100001 <= wage[i] <= 10000- Answers within
10^-5of the correct answer will be considered correct.
有N个工人，第i个工人的质量是quality[i]，最小工资期盼是wage[i]，现在想雇K个工人组成一个支付组，返回所需的最小花费。有两个条件：
1. K个工人的质量和给他开的工资的比例是相同的。
2. 每个工人都要满足他的最小期望工资。
解法：最大堆, heapq, PriorityQueue。首先对付工资和质量的比率进行排序wage/quality，同时记录quality，也就是(wage/quality, quality)，代表一个工人情况，比率越大说明工人效率越低。选定的K个人最后要按照相同的比率来支付工资，为了保证每个人的最低工资标准，只能选定比率最高的人的比率来支付工资。每个人的支付工资：wage = ratio * quality，总的支付工资：total wage = ratio * total quality，在ratio相同的情况小，总的quality越小越好。用一个变量result记录最小花费，初始为最大浮点数。循环排序好的工资比率，用一个变量qsum累加quality，用一个最大堆记录当前的quality，堆顶是最大的quality，如果堆长度等于K+1，就弹出quality最大的，同时qsum中去掉这个最大值。堆满足K个工人的时候，每次都计算qsum * ratio，和result比较取小的。
Java:
public double mincostToHireWorkers(int[] q, int[] w, int K) {
double[][] workers = new double[q.length][2];
for (int i = 0; i < q.length; ++i)
workers[i] = new double[]{(double)(w[i]) / q[i], (double)q[i]};
Arrays.sort(workers, (a, b) -> Double.compare(a[0], b[0]));
double res = Double.MAX_VALUE, qsum = 0;
PriorityQueue<Double> pq = new PriorityQueue<>();
for (double[] worker: workers) {
qsum += worker[1];
pq.add(-worker[1]);
if (pq.size() > K) qsum += pq.poll();
if (pq.size() == K) res = Math.min(res, qsum * worker[0]);
}
return res;
}
Python:
def mincostToHireWorkers(self, quality, wage, K):
workers = sorted([float(w) / q, q] for w, q in zip(wage, quality))
res = float('inf')
qsum = 0
heap = []
for r, q in workers:
heapq.heappush(heap, -q)
qsum += q
if len(heap) > K: qsum += heapq.heappop(heap)
if len(heap) == K: res = min(res, qsum * r)
return res
Python:
# Time: O(nlogn)
# Space : O(n)
import itertools
import heapq
class Solution(object):
def mincostToHireWorkers(self, quality, wage, K):
"""
:type quality: List[int]
:type wage: List[int]
:type K: int
:rtype: float
"""
workers = [[float(w)/q, q] for w, q in itertools.izip(wage, quality)]
workers.sort()
result = float("inf")
qsum = 0
max_heap = []
for r, q in workers:
qsum += q
heapq.heappush(max_heap, -q)
if len(max_heap) > K:
qsum -= -heapq.heappop(max_heap)
if len(max_heap) == K:
result = min(result, qsum*r)
return result
Python: O(nlogn) time,O(n) space
class Solution(object):
def mincostToHireWorkers(self, quality, wage, K):
"""
:type quality: List[int]
:type wage: List[int]
:type K: int
:rtype: float
"""
# 按比例排序,nlogn
workers = sorted([float(wage[i])/quality[i], quality[i]] for i in range(len(quality)))
res,qsum = float('inf'),0
heap = []
for i in range(len(workers)):
# 选定比例 r
r,q = workers[i]
heapq.heappush(heap,-q)
# qsum始终记录k个人的quality之和，乘以r即为最后结果
qsum += q
if len(heap) > K:
# 始终丢弃quality最大的人
qsum += heapq.heappop(heap)
if len(heap) == K:
res = min(res, qsum * r)
return res
C++:
double mincostToHireWorkers(vector<int> q, vector<int> w, int K) {
vector<vector<double>> workers;
for (int i = 0; i < q.size(); ++i)
workers.push_back({(double)(w[i]) / q[i], (double)q[i]});
sort(workers.begin(), workers.end());
double res = DBL_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;
}
C++:
// Time: O(nlogn)
// Space: O(n)
class Solution {
public:
double mincostToHireWorkers(vector<int>& quality, vector<int>& wage, int K) {
vector<pair<double, int>> workers;
for (int i = 0; i < quality.size(); ++i) {
workers.emplace_back(static_cast<double>(wage[i]) / quality[i],
quality[i]);
}
sort(workers.begin(), workers.end());
auto result = numeric_limits<double>::max();
auto sum = 0.0;
priority_queue<int> max_heap;
for (const auto& worker: workers) {
sum += worker.second;
max_heap.emplace(worker.second);
if (max_heap.size() > K) {
sum -= max_heap.top(), max_heap.pop();
}
if (max_heap.size() == K) {
result = min(result, sum * worker.first);
}
}
return result;
}
};