857. Minimum Cost of Hiring K Workers

857. Minimum Cost to Hire K Workers #

There are n workers. Given two arrays quality and wage, where quality[i] represents the work quality of the i-th worker and wage[i] represents the minimum expected wage for that worker.

Now, we want to hire k workers to form a wage group. When hiring a group of k workers, we must pay them wages according to the following rules:

For each worker in the wage group, the wage should be paid in proportion to their work quality compared to the work quality of other workers in the same group.
Each worker in the wage group should receive at least their minimum expected wage.

Given an integer k, return the minimum amount of money needed to form a wage group that satisfies the above conditions. Answers within $10^{-5}$ of the actual answer will be accepted.

Example 1:

Input: quality = [10,20,5], wage = [70,50,30], k = 2
Output: 105.00000
Explanation: We pay 70 to worker 0 and 35 to worker 2.

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 worker 0 and 13.33333 to workers 2 and 3.

Note:

$n == quality.length == wage.length$
$1 \leq k \leq n \leq 10^4$
$1 \leq quality[i], wage[i] \leq 10^4$

Priority Queue#

class Solution {
public:
    double mincostToHireWorkers(vector<int> &quality, vector<int> &wage, int k) {
        int n = quality.size();
        vector<int> h(n, 0);
        iota(h.begin(), h.end(), 0);
        sort(h.begin(), h.end(), [&](const int &a, const int &b) {
            return quality[a] * wage[b] > quality[b] * wage[a];
        });
        double res = 1e9;
        double totalq = 0.0;
        priority_queue<int, vector<int>, less<int>> q;
        for (int i = 0; i < k - 1; ++i) {
            totalq += quality[h[i]];
            q.push(quality[h[i]]);
        }
        for (int i = k - 1; i < n; ++i) {
            int idx = h[i];
            totalq += quality[idx];
            q.push(quality[idx]);
            double totalc = ((double)wage[idx] / quality[idx]) * totalq;
            res = min(res, totalc);
            totalq -= q.top();
            q.pop();
        }
        return res;
    }
};