Description#
There are n workers. You are given two integer arrays quality and wage where quality[i] is the quality of the ith worker and wage[i] is the minimum wage expectation for the ith worker.
We want to hire exactly k workers to form a paid group. To hire 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.
Given the integer k, return the least amount of money needed to form a paid group satisfying 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 0th worker and 35 to 2nd 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 0th worker, 13.33333 to 2nd and 3rd workers separately.
Constraints:
n == quality.length == wage.length1 <= k <= n <= 1041 <= quality[i], wage[i] <= 104
Solutions#
Solution 1#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| 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
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| 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;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution {
public:
double mincostToHireWorkers(vector<int>& quality, vector<int>& wage, int k) {
int n = quality.size();
vector<pair<double, int>> t(n);
for (int i = 0; i < n; ++i) {
t[i] = {(double) wage[i] / quality[i], quality[i]};
}
sort(t.begin(), t.end());
priority_queue<int> pq;
double ans = 1e9;
int tot = 0;
for (auto& [x, q] : t) {
tot += q;
pq.push(q);
if (pq.size() == k) {
ans = min(ans, tot * x);
tot -= pq.top();
pq.pop();
}
}
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
| 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
}
type pair struct {
x float64
q int
}
type hp struct{ sort.IntSlice }
func (h *hp) Push(v any) { h.IntSlice = append(h.IntSlice, v.(int)) }
func (h *hp) Pop() any {
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] }
|
