Minimum Cost to Hire K Workers
Hard · Heap & Counting · Array · Greedy · Sorting · Heap (Priority Queue)
Problem
There are n workers. Worker i has a quality quality[i] and a minimum wage expectation wage[i]. You want to hire exactly k of them as one paid group, following two rules:
- Within the group, pay is proportional to quality: a worker with twice the quality of another gets twice the pay.
- Every worker in the group is paid at least their minimum wage expectation.
Return the least total amount of money needed to form such a group. Answers within 10^-5 of the true value are accepted.
Examples
Input: quality = [4,2,8], wage = [8,6,24], k = 2 Output: 18.0
Workers 0 and 1 are paid 3 per unit of quality (worker 1 needs 6 / 2 = 3): 12 + 6 = 18.
Input: quality = [1,1,1], wage = [5,3,4], k = 3 Output: 15.0
Everyone has the same quality, so everyone is paid the highest demand, 5: 15 in all.
Input: quality = [10,20,5], wage = [70,50,30], k = 2 Output: 105.0
Workers 0 and 2 at 7 per unit cost 70 + 35 = 105. Worker 1 has the lowest ratio, 2.5, but any group with them costs at least 6 · 25 = 150.
Constraints
- n == len(quality) == len(wage)
- 1 <= k <= n <= 10^4
- 1 <= quality[i], wage[i] <= 10^4
Approaches
- Try every worker as the rate setter — time O(n² log n), space O(n)
Follow-up
The same "sort by one key, keep the best k of another key in a heap" pattern solves problems where a score is (sum of one attribute) times (min or max of another attribute) over a group of size k. Can you adapt it when the group may have at most k members, or when there is a budget and you want the largest group that fits?
Related problems
Start free on Cariara · Coding problems · System design studio
