Minimum Cost to Hire K Workers - Solution & Explanation
Problem Statement
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 must be paid at least their minimum wage expectation.
- In the group, each worker's pay must be directly proportional to their quality. This means if a worker’s quality is double that of another worker in the group, then they must be paid twice as much as the other worker.
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
Approach Overview
Problem 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.
Approach 1: Heap-Based Approach
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.
Complexity
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.
Approach 2: Sorting-Based Approach
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.
Complexity
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 3: Default Approach
Try this approach in the editor →Complexity Comparison
| 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 | — |
Detailed Complexity Analysis
| 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 |
Video Solution
Minimum Cost to Hire K Workers - Leetcode 857 - Python • NeetCodeIO • 20,604 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Minimum Cost to Hire K Workers easy or hard?
Minimum Cost to Hire K Workers Python/Java solution
How to solve Minimum Cost to Hire K Workers in O(n)?
What is the best approach for Minimum Cost to Hire K Workers?
Is Minimum Cost to Hire K Workers asked at Google/Amazon/Meta?
What data structure is used in Minimum Cost to Hire K Workers?
What is the time complexity of Minimum Cost to Hire K Workers?
Ready to solve this problem?
Practice Minimum Cost to Hire K Workers with our built-in code editor and test cases.
Practice on FleetCodeTable of Contents
Practice this problem
Open in Editor