Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/857.html
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:
- 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.
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/
// 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/
// 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;
}
};
-
class Solution { public double mincostToHireWorkers(int[] quality, int[] wage, int K) { int length = quality.length; int[][] qualityWageArray = new int[length][2]; for (int i = 0; i < length; i++) { qualityWageArray[i][0] = quality[i]; qualityWageArray[i][1] = wage[i]; } Arrays.sort(qualityWageArray, new Comparator<int[]>() { public int compare(int[] qualityWage1, int[] qualityWage2) { return qualityWage1[1] * qualityWage2[0] - qualityWage1[0] * qualityWage2[1]; } }); double ratio = 0; int totalQuality = 0; PriorityQueue<Integer> priorityQueue = new PriorityQueue<Integer>(new Comparator<Integer>() { public int compare(Integer num1, Integer num2) { return num2 - num1; } }); for (int i = 0; i < K; i++) { int[] qualityWage = qualityWageArray[i]; int curQuality = qualityWage[0], curWage = qualityWage[1]; totalQuality += curQuality; priorityQueue.offer(curQuality); double curRatio = 1.0 * curWage / curQuality; ratio = Math.max(ratio, curRatio); } double minCost = totalQuality * ratio; for (int i = K; i < length; i++) { int prevQuality = priorityQueue.poll(); totalQuality -= prevQuality; int[] qualityWage = qualityWageArray[i]; int curQuality = qualityWage[0], curWage = qualityWage[1]; totalQuality += curQuality; priorityQueue.offer(curQuality); double curRatio = 1.0 * curWage / curQuality; ratio = Math.max(ratio, curRatio); double curCost = totalQuality * ratio; minCost = Math.min(minCost, curCost); } return minCost; } } ############ class Solution { public double mincostToHireWorkers(int[] quality, int[] wage, int k) { int n = quality.length; Pair[] t = new Pair[n]; for (int i = 0; i < n; ++i) { t[i] = new Pair(quality[i], wage[i]); } Arrays.sort(t, (a, b) -> Double.compare(a.x, b.x)); PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> b - a); double ans = 1e9; int tot = 0; for (var e : t) { tot += e.q; pq.offer(e.q); if (pq.size() == k) { ans = Math.min(ans, tot * e.x); tot -= pq.poll(); } } return ans; } } class Pair { double x; int q; Pair(int q, int w) { this.q = q; this.x = (double) w / q; } } -
// OJ: https://leetcode.com/problems/minimum-cost-to-hire-k-workers/ // 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; } }; -
class Solution: def mincostToHireWorkers( self, quality: List[int], wage: List[int], k: int ) -> float: t = sorted(zip(quality, wage), key=lambda x: x[1] / x[0]) ans, tot = inf, 0 h = [] for q, w in t: tot += q heappush(h, -q) if len(h) == k: ans = min(ans, w / q * tot) tot += heappop(h) return ans ############ class Solution(object): def mincostToHireWorkers(self, quality, wage, K): """ :type quality: List[int] :type wage: List[int] :type K: int :rtype: float """ works = sorted([(w / float(q), q) for w, q in zip(wage, quality)]) que = [] qsum = 0 res = float("inf") for rate, q in works: heapq.heappush(que, -q) qsum += q if len(que) > K: qsum += heapq.heappop(que) if len(que) == K: res = min(res, qsum * rate) return res -
func mincostToHireWorkers(quality []int, wage []int, k int) float64 { t := []pair{} for i, q := range quality { t = append(t, pair{float64(wage[i]) / float64(q), q}) } sort.Slice(t, func(i, j int) bool { return t[i].x < t[j].x }) tot := 0 var ans float64 = 1e9 pq := hp{} for _, e := range t { tot += e.q heap.Push(&pq, e.q) if pq.Len() == k { ans = min(ans, float64(tot)*e.x) tot -= heap.Pop(&pq).(int) } } return ans } func min(a, b float64) float64 { if a < b { return a } return b } type pair struct { x float64 q int } type hp struct{ sort.IntSlice } func (h *hp) Push(v interface{}) { h.IntSlice = append(h.IntSlice, v.(int)) } func (h *hp) Pop() interface{} { a := h.IntSlice v := a[len(a)-1] h.IntSlice = a[:len(a)-1] return v } func (h *hp) Less(i, j int) bool { return h.IntSlice[i] > h.IntSlice[j] }