857

857. Minimum Cost to Hire K Workers (Hard)

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.

Related Topics:
Heap

TLE version. Greedy

Try person[i] as the baseline. Use her W[i] / Q[i] as the factor to get others' wages. Drop those who can't meet their min wages.

For the rest, sum the smallest K wages.

// OJ: https://leetcode.com/problems/minimum-cost-to-hire-k-workers/
// Author: github.com/lzl124631x
// Time: O(N^2 * logN)
// Space: O(N)
// Ref: https://leetcode.com/problems/minimum-cost-to-hire-k-workers/solution/
// NOTE: this solution will get TLE
class Solution {
public:
    double mincostToHireWorkers(vector<int>& Q, vector<int>& W, int K) {
        int N = Q.size();
        double ans = DBL_MAX;
        for (int i = 0; i < N; ++i) {
            double factor = (double) W[i] / Q[i];
            vector<double> costs;
            for (int j = 0; j < N; ++j) {
                double c = factor * Q[j];
                if (c < W[j]) continue;
                costs.push_back(c);
            }
            if (costs.size() < K) continue;
            sort(costs.begin(), costs.end());
            double sum = accumulate(costs.begin(), costs.begin() + K, 0.0);
            ans = min(ans, sum);
        }
        return ans;
    }
};

Solution 1. Max Heap

If we select person[i] as the benchmark, W[i]/Q[i] will be used as the rate. All other people get Q[j] * rate.

If Q[j] * rate[i] is smaller than W[j], i.e. Q[j] * rate[i] < W[j], or rate[i] < rate[j], person[j] can't work.

So rate[i] can only make the people with equal or smaller rates to be able to work.

• The greatest rate can make all people work, but results in greater total wage.
• The smaller rate can make less people work, but results in smaller total wage.

Hence we can iterate people in ascending order of rate.

We use a max heap pq to keep the qualities of people, and sum to track the sum of qualities of people in the pq.

For person[i], we add her quality into the pq. And pop if the pq has more than K people. We update the sum accordingly.

If there are K people in the pq, then sum * rate[i] is the total wage. We just need to find the minimal total wage.

// OJ: https://leetcode.com/problems/minimum-cost-to-hire-k-workers/
// Author: github.com/lzl124631x
// Time: O(NlogN)
// Space: O(N)
class Solution {
public:
    double mincostToHireWorkers(vector<int>& Q, vector<int>& W, int K) {
        int N = Q.size(), sum = 0;
        double ans = DBL_MAX; 
        vector<int> id(N);
        vector<double> rate(N);
        for (int i = 0; i < N; ++i) rate[i] = (double)W[i] / Q[i];
        iota(begin(id), end(id), 0);
        sort(begin(id), end(id), [&](int a, int b) { return rate[a] < rate[b]; });
        priority_queue<int> pq;
        for (int i = 0; i < N; ++i) {
            sum += Q[id[i]];
            pq.push(Q[id[i]]);
            if (pq.size() > K) {
                sum -= pq.top();
                pq.pop();
            }
            if (pq.size() == K) ans = min(ans, rate[id[i]] * sum);
        }
        return ans;
    }
};