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:
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] <= 104Problem Overview: You are given two arrays: quality and wage. Each worker has a minimum wage expectation and a work quality. When hiring a group of k workers, everyone must be paid using the same wage-to-quality ratio, and each worker must receive at least their minimum wage. The goal is to choose k workers with the smallest possible total cost.
Approach 1: Sorting-Based Greedy Scan (O(n^2 log n) time, O(n) space)
The key constraint is that if a worker with ratio wage[i] / quality[i] sets the payment rate, every other worker must be paid using at least that ratio. Start by computing this ratio for every worker and sorting workers by it using sorting. Treat each worker as the "captain" who defines the group ratio. For that ratio, you want the k workers with the smallest total quality among all workers seen so far, because total cost equals ratio * sum(quality). A simple but slower method repeatedly collects candidate qualities and sorts them to pick the smallest k. This works conceptually but becomes inefficient as the candidate set grows.
Approach 2: Greedy + Max Heap (O(n log n) time, O(n) space)
The optimal solution improves the previous idea by maintaining the k smallest qualities dynamically. First compute each worker’s ratio and sort workers by ratio ascending. Iterate through the sorted list and keep a running group of workers. Track the sum of qualities and store qualities inside a max heap using a heap (priority queue). If the heap grows larger than k, remove the worker with the largest quality because that worker contributes the most to the cost. When the heap size reaches exactly k, compute the total cost as current_ratio * quality_sum. Since ratios increase as you iterate, each step evaluates the cheapest possible group whose highest ratio is the current worker. This greedy choice ensures the minimum cost.
The algorithm works because the payment ratio must match the highest ratio in the chosen group. Sorting guarantees that once a worker defines the ratio, all earlier workers already satisfy it. The heap keeps the quality sum minimal, which directly minimizes total payment.
Recommended for interviews: The greedy + max heap approach is the expected solution. It combines greedy reasoning with efficient data structures and runs in O(n log n). Interviewers often accept the conceptual greedy explanation first, then expect the heap optimization to maintain the smallest k qualities efficiently.
This approach uses a heap to dynamically maintain workers while iterating over them sorted by wage-to-quality ratio. The goal is to keep the sum of qualities of the selected workers minimal while ensuring all conditions are satisfied. We sort all workers by their wage-to-quality ratio because for each worker, to satisfy both their minimum wage and relative payment constraints, each selected worker must be paid at least this ratio times their quality.
The solution begins by sorting each worker by their wage-to-quality ratio. It then uses a max-heap to maintain the k workers with the smallest sum of qualities. For each worker evaluated, we add their quality to the max heap. If the max heap exceeds k in size, we remove the largest quality to ensure we're considering the smallest k qualities. The current cost calculated by multiplying the present worker's rate with the sum of qualities in the heap is considered as a potential minimum.
Time Complexity: O(n log n) due to sorting, and O(n log k) for heap operations.
Space Complexity: O(n) for the sorted list of workers or the heap.
This approach focuses on sorting workers by the ratio of their wage expectation to quality. By calculating this ratio, we can use it as a reference point to determine the required payment for every possible group of k workers. Selecting the right workers and calculating the minimum payment by understanding proportional wages can be done by iterating over sorted worker lists using two indices, capturing the required details and performing the necessary calculations.
Here, the Python code sorts workers by their ratio of wage to quality. A max-heap manages the quality selection, and when a potential solution with k workers is found, the resultant cost is calculated. The approach makes efficient use of sorted ratios and quality management to derive the answer.
Time Complexity: O(n log n) due to sorting, and O(n log n) due to managing heap.
Space Complexity: O(n) for worker list and heap storage.
| Approach | Complexity |
|---|---|
| Heap-Based Approach | Time Complexity: O(n log n) due to sorting, and O(n log k) for heap operations. |
| Sorting-Based Approach | Time Complexity: O(n log n) due to sorting, and O(n log n) due to managing heap. |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sorting-Based Greedy Scan | O(n^2 log n) | O(n) | Useful for understanding the ratio insight before optimizing with a heap |
| Greedy + Max Heap (Priority Queue) | O(n log n) | O(n) | Optimal solution for interviews and large inputs |
Minimum Cost to Hire K Workers - Leetcode 857 - Python • NeetCodeIO • 19,881 views views
Watch 9 more video solutions →Practice Minimum Cost to Hire K Workers with our built-in code editor and test cases.
Practice on FleetCode