Minimum Cost to Hire K Workers
Asked at Apple
Problem
Given N workers with quality and minimum wage expectations, hire exactly K workers such that the total cost is minimized. Each hired worker must be paid proportionally based on their quality-to-wage ratio. This problem combines greedy sorting with heap-based optimization.
Asked At
| Company | Difficulty | |
|---|---|---|
| Apple | HARD | View all Apple questions → |
How to Think About It
Compute the wage-to-quality ratio for each worker and sort by this ratio
Iterate through workers sorted by ratio, treating each as the ratio-defining worker
Maintain a max-heap of K-1 qualities from previously seen workers
For each worker, the cost is the sum of K-1 largest qualities times the current ratio
Track the minimum cost across all possible ratio-defining workers
Optimal Approach
Sort workers by their wage-to-quality ratio. For each worker i (in sorted order), assume worker i defines the group ratio (all workers are paid at quality[i] * ratio_i). To minimize cost with this ratio, pick K-1 workers from among those with ratio <= ratio_i who have the smallest qualities. Use a max-heap to maintain the K-1 smallest qualities. When the heap reaches size K-1, the cost is (sum of heap + quality[i]) * ratio_i. Track the minimum cost. The key insight is that the highest-ratio worker in any group determines the pay rate.
What Trips People Up in Real Interviews
Clarify that pay is proportional: paid[i] = quality[i] * ratio
Explain that the worker with the highest ratio determines the group ratio
Mention why sorting by ratio and using a max-heap gives the optimal solution
Discuss that the heap maintains the K-1 workers with smallest quality from previous groups
State the time complexity is O(N log N) for sorting and O(N log K) for heap operations
Solution Code
import heapq
class Solution:
def mincostToHireWorkers(self, quality: list[int], wage: list[int], k: int) -> float:
workers = sorted([(w / q, q) for q, w in zip(quality, wage)])
result = float('inf')
total_quality = 0
max_heap = []
for ratio, q in workers:
total_quality += q
heapq.heappush(max_heap, -q)
if len(max_heap) > k:
total_quality += heapq.heappop(max_heap)
if len(max_heap) == k:
result = min(result, total_quality * ratio)
return resultFrequently Asked Questions
What is the Minimum Cost to Hire K Workers problem?
Given N workers with quality and minimum wage expectations, hire exactly K workers such that the total cost is minimized. Each hired worker must be paid proportionally based on their quality-to-wage ratio. This problem combines greedy sorting with heap-based optimization.
How do you solve Minimum Cost to Hire K Workers?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Minimum Cost to Hire K Workers?
Minimum Cost to Hire K Workers is asked at Apple. It is a hard difficulty problem.
What are common mistakes on Minimum Cost to Hire K Workers?
- Clarify that pay is proportional: paid[i] = quality[i] * ratio
- Explain that the worker with the highest ratio determines the group ratio
- Mention why sorting by ratio and using a max-heap gives the optimal solution
- Discuss that the heap maintains the K-1 workers with smallest quality from previous groups
- State the time complexity is O(N log N) for sorting and O(N log K) for heap operations