DSA problem
Minimum Cost to Hire K Workers
There are n workers. You are given two integer arrays quality and wage where quality[i] is the quality of the i-th worker and wage[i] is the minimum wage expectation of the i-th 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 must be paid in the ratio of their quality compared to other workers in the group, and 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.
Define each worker's ratio r_i = wage_i / quality_i — the minimum money the manager spends per unit of quality. If we hire a group with manager ratio R, the total cost is R * sum(quality_in_group). For each worker in the group to be paid at least their minimum wage, R must be at least every worker's r_i. So the chosen R is the maximum ratio across the hired group.
This points to a two-step greedy. First, sort workers by their ratio ascending; iterate in that order so the current worker provides the candidate maximum ratio R = r_i. Second, we want to minimize R * sum(quality) for the chosen group — which means, given a fixed R, we pick the k workers with the smallest qualities seen so far. A max-heap of the chosen qualities (pop the largest when the heap exceeds size k) maintains exactly the k smallest qualities among the first i workers.
Walk the sorted array, push each worker's quality, evict the largest if the heap exceeds k. When the heap has exactly k elements, compute R * sum using the current worker's ratio and update the running minimum. Time complexity is O(n log n) for sorting plus O(n log k) for the heap; space is O(k).
Examples
quality = [10,20,5], wage = [70,50,30], k = 2105.00000quality = [3,1,10,10,1], wage = [4,8,2,2,7], k = 330.66667quality = [5,5,5], wage = [10,10,10], k = 220.00000Constraints
- n == quality.length == wage.length
- 1 <= k <= n <= 10^4
- 1 <= quality[i], wage[i] <= 10^4
- Answers within 10^-5 of the actual answer are accepted.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.