n workers. You are given two integer arrays
quality[i] is the quality of the
ith worker and
wage[i] is the minimum wage expectation for the
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.
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.
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.
n == quality.length == wage.length
1 <= k <= n <= 104
1 <= quality[i], wage[i] <= 104
Use a heap to find worker qualities from high to low.
To find k workers is to find k workers with .
class Solution: def mincostToHireWorkers(self, quality: List[int], wage: List[int], k: int) -> float: workers =  for w,q in zip(wage, quality): workers.append((w/q, w, q)) workers = sorted(workers) heap =  min_cost = sys.maxsize quality_sum = 0 for ratio, wage, quality in workers: heapq.heappush(heap, -quality) quality_sum += quality if len(heap) > k: quality_sum += heapq.heappop(heap) if len(heap) == k: min_cost = min(min_cost, ratio * quality_sum) return min_cost
- Time Complexity: O(N log (N))
- Space Complexity: O(N)