[LeetCode] 857. Minimum Cost to Hire K Workers

[grandyang]

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:

1. Every worker in the paid group should be paid in the ratio of their quality compared to other workers in the paid group.
2. 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. 1 <= K <= N <= 10000, where N = quality.length = wage.length
2. 1 <= quality[i] <= 10000
3. 1 <= wage[i] <= 10000
4. Answers within 10^-5 of the correct answer will be considered correct.

这道题说是有N个员工，每个员工有个能力值，还有个薪水期望值，现在我们需要从中雇佣K个员工，需要满足两个条件：1. 每个员工的薪水要和其能力值成恒定比例。2. 每个员工的薪水不低于其期望值。让求雇佣满足要求的K个员工的最小花费是多少，博主最开始看到这题时，以为是背包问题，又看了一下是 Hard 的难度，更加坚定了是个 DP 问题。但实际上这却是一道贪婪算法能解决的问题，类型标签给的是堆 Heap，嗯，因缺斯汀。我们仔细来分析分析题目中限定必须满足的两个条件，先来看第一个，说是每个员工的薪水要和其能力值成恒定比例，意思是说假如两个员工A和B，若A的能力值是B的2倍，那么A的薪水就要是B的两倍，要雇佣的K个员工所有人的薪水和能力都是要成比例的，而这个比例一定是个恒定值，只要能够算出这个最低的薪水能力比例值，乘以K个员工的总能力值，就可以得到最少的总花费。第二个需要满足的条件是每个员工的薪水不能低于其期望值，则每个员工都有一个自己固定的薪水能力比例值，而需要求的那个最低的薪水能力比例值不能小于任何一个员工自己的比例值。当员工能力值越低，期望薪水越高的时候，其薪水能力比例值就越大，所以可以根据薪水能力比例值从大到小来排列员工。可以将员工的薪水能力比例值和其能力值组成 pair 对儿放到一个数组中，然后对这个数组进行排序，则默认就是对薪水能力比例值进行从小到大的排列。接下来的操作就跟之前那道 Top K Frequent Words 非常像了，这里用一个最大堆，还要用一个变量 qsum 来累加员工的能力值，先将薪水能力比例最低的员工的能力值加到 qsum 中，同时加入到最大堆中，若堆中员工总数大于K了，则将堆顶能力值最大的员工移除，因为能力值越大意味着需要付的薪水越多。若堆中员工总数等于K了，则用当前员工的薪水能力比例乘以总的能力值数得到一个总花费，用来更新结果 res。为啥这样是正确的呢？因为当前员工的薪水能力比例值是大于堆中其他所有员工的，那么乘以恒定的总能力值，得出的总薪水数一定大于等于使用其他员工的薪水能力比例值，则每个员工可得到的薪水一定是大于等于其期望值的，这样就同时满足了两个条件，所以是符合题意的，最终更新完得到的总花费一定是最低的，参见代码如下：

class Solution {
public:
    double mincostToHireWorkers(vector<int>& quality, vector<int>& wage, int K) {
        double res = DBL_MAX, qsum = 0, n = quality.size();
        vector<pair<double, int>> workers;
        priority_queue<int> pq;
        for (int i = 0; i < n; ++i) {
            workers.push_back({double(wage[i]) / quality[i], quality[i]});
        }
        sort(workers.begin(), workers.end());
        for (auto worker : workers) {
            qsum += worker.second;
            pq.push(worker.second);
            if (pq.size() > K) {
                qsum -= pq.top(); pq.pop();
            }
            if (pq.size() == K) {
                res = min(res, qsum * worker.first);
            }
        }
        return res;
    }
};

Github 同步地址:

#857

类似题目：

Top K Frequent Words

参考资料：

https://leetcode.com/problems/minimum-cost-to-hire-k-workers/

https://leetcode.com/problems/minimum-cost-to-hire-k-workers/discuss/185085/75ms-Java-with-Explanations

https://leetcode.com/problems/minimum-cost-to-hire-k-workers/discuss/141768/Detailed-explanation-O(NlogN)

LeetCode All in One 题目讲解汇总(持续更新中...)