Minimum Cost to Hire K Workers - Video Solutions
Minimum Cost to Hire K Workers - Leetcode 857 - Python
Minimum Cost to Hire K Workers - Video Solution
Watch 10 video solutions for Minimum Cost to Hire K Workers, a hard level problem involving Array, Greedy, Sorting. This walkthrough by NeetCodeIO has 20,604 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
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 |