Leet Code Daily 2024-05-11 - Minimum Cost to Hire K Workers

Description

Solution

Let's say $H$ is the set of hired workers and $C_i$ is the cost of hired worker $i$ .

\lvert H \rvert = k

We know all hired workers must be paid equally.

\text{Given } H, \text{for each } i \in H, \frac{C_i}{Q_i} = p

And we also know the minimum wage $W_i$ .

C_i = Q_i \times p \geq W_i

p \geq \frac{W_i}{Q_i}

The total cost would be:

\sum_{i \in H}{p \times Q_i}

Sort + Priority Queue

If we sort all workers by $\frac{W_i}{Q_i}$ . Then, at any time, if worker $i$ is hired, all workers before $i$ can be hired with same $p = \frac{W_i}{Q_i}$ . And we only need to maintain top-k workers with smallest $Q_i$ before to find current minimum cost.

Time Complexity

O(n \log_2{n})

Code

c++

class Solution {
public:
    double mincostToHireWorkers(vector<int>& quality, vector<int>& wage,
                                int k) {
        vector<pair<int, int>> workers;
        for (int i = 0; i < quality.size(); i++) {
            workers.push_back(make_pair(quality[i], wage[i]));
        }
        sort(workers.begin(), workers.end(),
             [](const pair<int, int>& x, const pair<int, int>& y) {
                 return x.second * y.first < y.second * x.first;
             });
        double ans = 1E9;
        int total_quality = 0;
        priority_queue<int> hired_workers;
        for (const auto& w : workers) {
            total_quality += w.first;
            hired_workers.push(w.first);
            while (hired_workers.size() > k) {
                total_quality -= hired_workers.top();
                hired_workers.pop();
            }
            if (hired_workers.size() == k) {
                ans = min(ans, 1.0 * total_quality * w.second / w.first);
            }
        }
        return ans;
    }
};

Leet Code Daily 2024-05-11 - Minimum Cost to Hire K Workers

Solution

Sort + Priority Queue

Time Complexity

Code

COMMAND INTERFACE

:help aguang.xyz