LeetCode 857 - Minimum Cost to Hire K Workers
In this problem, we are given two arrays, quality and wage, where each index represents a worker. The value quality[i] describes how much work or contribution the i-th worker provides, while wage[i] describes the minimum amount that worker is willing to accept.
Difficulty: 🔴 Hard
Topics: Array, Greedy, Sorting, Heap (Priority Queue)
Solution
Problem Understanding
In this problem, we are given two arrays, quality and wage, where each index represents a worker. The value quality[i] describes how much work or contribution the i-th worker provides, while wage[i] describes the minimum amount that worker is willing to accept.
We must hire exactly k workers, and the group must satisfy two rules simultaneously.
First, every worker must receive at least their minimum wage expectation.
Second, the pay structure inside the group must be proportional to quality. If worker A has twice the quality of worker B, then worker A must receive exactly twice the pay of worker B.
This proportionality constraint is the core difficulty of the problem. Once a group is chosen, there is effectively a single "pay rate per quality unit" shared across the entire group. If the rate is r, then a worker with quality q must be paid:
$$\text{pay} = r \times q$$
For a worker to accept the offer, we must ensure:
$$r \times q_i \geq wage_i$$
Rearranging this gives:
$$r \geq \frac{wage_i}{quality_i}$$
This ratio is extremely important. It tells us the minimum pay-per-quality rate that each worker requires.
For any selected group, the actual rate r must be at least the maximum ratio among all workers in the group. Once that rate is fixed, every worker's salary becomes determined automatically.
The total cost of hiring a group becomes:
$$\text{total cost} = r \times (\text{sum of qualities})$$
The constraints are large enough that brute force enumeration of all possible groups is infeasible. Since n can be as large as 10^4, any exponential or combinatorial approach will time out. We need something close to O(n log n).
Several edge cases are important:
- When
k = 1, we simply choose the worker with the smallest wage. - Workers can have identical ratios.
- Workers can have extremely different qualities, which affects the total cost heavily.
- A worker with a low wage but extremely high quality may still be expensive overall.
- Floating-point precision matters because the answer accepts an error tolerance of
10^-5.
Approaches
Brute Force Approach
The brute force solution would generate every possible group of k workers. For each group, we would determine the required pay rate by taking the maximum value of:
$$\frac{wage_i}{quality_i}$$
among all workers in the group.
Once the rate is known, we compute:
$$\text{cost} = \text{rate} \times \text{sum of qualities}$$
We would track the minimum cost across all groups.
This works because every valid group must use a pay rate at least as large as the highest required ratio in that group. Using exactly that maximum ratio minimizes the total cost for the chosen group.
However, this approach is far too slow. The number of combinations is:
$$\binom{n}{k}$$
which becomes enormous even for moderate values of n.
Optimal Greedy + Heap Approach
The key observation is that if we fix the highest ratio in a group, then the total cost depends only on the sum of qualities.
Suppose worker i has the highest ratio in the group:
$$r_i = \frac{wage_i}{quality_i}$$
Then every worker in the group must be paid using this same rate r_i.
The total cost becomes:
$$r_i \times (\text{sum of qualities})$$
For a fixed ratio, minimizing cost means minimizing the sum of qualities.
This leads to a greedy strategy:
- Sort workers by ratio in ascending order.
- Process workers from smallest ratio to largest.
- Treat the current worker's ratio as the group's maximum ratio.
- Among all workers seen so far, keep the
kworkers with the smallest total quality.
To efficiently maintain the smallest quality sum, we use a max heap. Whenever the heap grows beyond size k, we remove the worker with the largest quality because that worker contributes the most to increasing total cost.
This gives an efficient O(n log n) solution.
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | $O\left(\binom{n}{k} \cdot k\right)$ | O(k) | Enumerates every possible group |
| Optimal | O(n log n) | O(k) | Greedy sorting with max heap |
Algorithm Walkthrough
- Create a list of workers where each worker stores:
- their wage-to-quality ratio
- their quality
The ratio is:
$$\frac{wage[i]}{quality[i]}$$
This ratio represents the minimum pay-per-quality rate the worker will accept. 2. Sort all workers by ratio in ascending order.
After sorting, when processing worker i, their ratio becomes the highest ratio among all workers considered so far.
3. Maintain a max heap containing worker qualities.
The heap helps us efficiently keep track of the smallest possible total quality among candidate workers. 4. Maintain a running sum of qualities.
Every time we add a worker to the heap, we increase the quality sum. 5. Iterate through workers in sorted ratio order.
For each worker:
- add their quality to the heap
- add their quality to the running sum
- If the heap size exceeds
k, remove the worker with the largest quality.
We remove the largest quality because it contributes the most to increasing total cost. Removing it gives the smallest possible quality sum for the current ratio.
7. Whenever the heap size becomes exactly k, compute the total cost:
$$\text{cost} = (\text{current ratio}) \times (\text{quality sum})$$
Update the minimum answer if this cost is smaller. 8. Continue until all workers are processed.
Why it works
The correctness comes from the fact that the current worker's ratio is the maximum allowable ratio for the current group. Since all workers before it have ratios less than or equal to the current ratio, they can all legally be paid using this rate.
For a fixed ratio, minimizing total cost is equivalent to minimizing total quality. The heap guarantees that among all valid candidates seen so far, we always keep the k workers with the smallest possible total quality.
Therefore, every candidate group considered is optimal for its maximum ratio, and checking all possible maximum ratios guarantees the global optimum.
Python Solution
from typing import List
import heapq
class Solution:
def mincostToHireWorkers(
self,
quality: List[int],
wage: List[int],
k: int
) -> float:
workers = []
for q, w in zip(quality, wage):
ratio = w / q
workers.append((ratio, q))
workers.sort()
max_heap = []
quality_sum = 0
minimum_cost = float("inf")
for ratio, q in workers:
heapq.heappush(max_heap, -q)
quality_sum += q
if len(max_heap) > k:
removed_quality = -heapq.heappop(max_heap)
quality_sum -= removed_quality
if len(max_heap) == k:
total_cost = ratio * quality_sum
minimum_cost = min(minimum_cost, total_cost)
return minimum_cost
The implementation begins by constructing a list of workers containing their ratio and quality. We only need these two values because once the ratio is known, the wage itself is no longer necessary.
The workers are sorted by ratio so that while iterating, the current worker always defines the maximum ratio in the candidate group.
Python's heapq module implements a min heap, but we need a max heap so we store negative qualities. This allows efficient removal of the largest quality whenever the heap size exceeds k.
The variable quality_sum tracks the total quality of workers currently inside the heap. When we remove a worker, we subtract their quality from the running sum.
Whenever the heap contains exactly k workers, we compute the candidate total cost using the current ratio and the current quality sum. Since the heap always maintains the smallest possible quality sum for this ratio, the computed cost is optimal for this ratio.
The minimum across all such candidate costs is returned.
Go Solution
package main
import (
"container/heap"
"sort"
)
type MaxHeap []int
func (h MaxHeap) Len() int {
return len(h)
}
func (h MaxHeap) Less(i, j int) bool {
return h[i] > h[j]
}
func (h MaxHeap) Swap(i, j int) {
h[i], h[j] = h[j], h[i]
}
func (h *MaxHeap) Push(x interface{}) {
*h = append(*h, x.(int))
}
func (h *MaxHeap) Pop() interface{} {
old := *h
n := len(old)
value := old[n-1]
*h = old[:n-1]
return value
}
type Worker struct {
ratio float64
quality int
}
func mincostToHireWorkers(quality []int, wage []int, k int) float64 {
n := len(quality)
workers := make([]Worker, n)
for i := 0; i < n; i++ {
workers[i] = Worker{
ratio: float64(wage[i]) / float64(quality[i]),
quality: quality[i],
}
}
sort.Slice(workers, func(i, j int) bool {
return workers[i].ratio < workers[j].ratio
})
maxHeap := &MaxHeap{}
heap.Init(maxHeap)
qualitySum := 0
answer := 1e18
for _, worker := range workers {
heap.Push(maxHeap, worker.quality)
qualitySum += worker.quality
if maxHeap.Len() > k {
removed := heap.Pop(maxHeap).(int)
qualitySum -= removed
}
if maxHeap.Len() == k {
cost := worker.ratio * float64(qualitySum)
if cost < answer {
answer = cost
}
}
}
return answer
}
The Go implementation follows the same algorithmic structure as the Python version. The primary difference is that Go requires explicit heap implementation using the container/heap interface.
The heap is implemented as a max heap by reversing the comparison inside the Less method.
Go also requires explicit floating-point conversion when dividing integers, otherwise integer division would occur.
Unlike Python, Go does not have built-in tuple sorting, so a custom Worker struct and sort.Slice comparator are used.
Worked Examples
Example 1
Input:
quality = [10,20,5]
wage = [70,50,30]
k = 2
First compute ratios:
| Worker | Quality | Wage | Ratio |
|---|---|---|---|
| 0 | 10 | 70 | 7.0 |
| 1 | 20 | 50 | 2.5 |
| 2 | 5 | 30 | 6.0 |
After sorting by ratio:
| Order | Ratio | Quality |
|---|---|---|
| 1 | 2.5 | 20 |
| 2 | 6.0 | 5 |
| 0 | 7.0 | 10 |
Now process workers.
| Step | Current Ratio | Heap Qualities | Quality Sum | Cost |
|---|---|---|---|---|
| 1 | 2.5 | [20] | 20 | not enough workers |
| 2 | 6.0 | [20, 5] | 25 | 6 × 25 = 150 |
| 3 | 7.0 | [20, 5, 10] | 35 | remove 20 |
After removing largest quality:
| Heap | Quality Sum |
|---|---|
| [10, 5] | 15 |
Now compute:
$$7 \times 15 = 105$$
Minimum answer is 105.
Example 2
Input:
quality = [3,1,10,10,1]
wage = [4,8,2,2,7]
k = 3
Compute ratios:
| Worker | Quality | Wage | Ratio |
|---|---|---|---|
| 0 | 3 | 4 | 1.3333 |
| 1 | 1 | 8 | 8.0 |
| 2 | 10 | 2 | 0.2 |
| 3 | 10 | 2 | 0.2 |
| 4 | 1 | 7 | 7.0 |
Sorted order:
| Ratio | Quality |
|---|---|
| 0.2 | 10 |
| 0.2 | 10 |
| 1.3333 | 3 |
| 7.0 | 1 |
| 8.0 | 1 |
Processing:
| Step | Ratio | Heap | Quality Sum | Cost |
|---|---|---|---|---|
| 1 | 0.2 | [10] | 10 | incomplete |
| 2 | 0.2 | [10,10] | 20 | incomplete |
| 3 | 1.3333 | [10,10,3] | 23 | 30.6667 |
| 4 | 7.0 | [10,10,3,1] | 24 | remove 10 |
| 4 after removal | 7.0 | [10,3,1] | 14 | 98 |
| 5 | 8.0 | [10,3,1,1] | 15 | remove 10 |
| 5 after removal | 8.0 | [3,1,1] | 5 | 40 |
Minimum cost remains:
$$30.66667$$
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(n log n) | Sorting dominates, heap operations are logarithmic |
| Space | O(k) | Heap stores at most k workers |
Sorting the workers requires O(n log n) time. Each worker is inserted into the heap once and possibly removed once. Heap operations take O(log k) time, which is bounded by O(log n).
The heap never stores more than k + 1 workers, so the auxiliary space usage is O(k).
Test Cases
from typing import List
import math
class Solution:
def mincostToHireWorkers(
self,
quality: List[int],
wage: List[int],
k: int
) -> float:
import heapq
workers = []
for q, w in zip(quality, wage):
workers.append((w / q, q))
workers.sort()
heap = []
quality_sum = 0
answer = float("inf")
for ratio, q in workers:
heapq.heappush(heap, -q)
quality_sum += q
if len(heap) > k:
quality_sum -= -heapq.heappop(heap)
if len(heap) == k:
answer = min(answer, ratio * quality_sum)
return answer
solution = Solution()
# Provided example 1
assert math.isclose(
solution.mincostToHireWorkers([10,20,5], [70,50,30], 2),
105.0,
rel_tol=1e-5
)
# Provided example 2
assert math.isclose(
solution.mincostToHireWorkers([3,1,10,10,1], [4,8,2,2,7], 3),
30.6666666667,
rel_tol=1e-5
)
# Single worker case
assert math.isclose(
solution.mincostToHireWorkers([5], [10], 1),
10.0,
rel_tol=1e-5
)
# All workers must be hired
assert math.isclose(
solution.mincostToHireWorkers([1,2,3], [10,20,30], 3),
60.0,
rel_tol=1e-5
)
# Equal ratios
assert math.isclose(
solution.mincostToHireWorkers([2,4,6], [10,20,30], 2),
30.0,
rel_tol=1e-5
)
# Large quality difference
assert math.isclose(
solution.mincostToHireWorkers([100,1], [1000,2], 1),
2.0,
rel_tol=1e-5
)
# Optimal group excludes large quality worker
assert math.isclose(
solution.mincostToHireWorkers([10,100,5], [70,500,30], 2),
105.0,
rel_tol=1e-5
)
# Minimum k
assert math.isclose(
solution.mincostToHireWorkers([4,8,2], [20,40,10], 1),
10.0,
rel_tol=1e-5
)
# Maximum flexibility with same ratios
assert math.isclose(
solution.mincostToHireWorkers([1,2,3,4], [10,20,30,40], 2),
30.0,
rel_tol=1e-5
)
| Test | Why |
|---|---|
| Example 1 | Validates standard case |
| Example 2 | Validates floating-point behavior |
| Single worker case | Tests k = 1 |
| All workers hired | Tests k = n |
| Equal ratios | Ensures proportional logic works correctly |
| Large quality difference | Ensures quality sum minimization matters |
| Excluding large worker | Verifies heap removal logic |
| Minimum k | Tests smallest possible group |
| Same ratios with multiple choices | Ensures best quality sum is selected |
Edge Cases
One important edge case occurs when k = 1. In this scenario, proportional payment constraints become trivial because only one worker is being hired. A buggy implementation might still overcomplicate the ratio handling. The current implementation naturally handles this case because the heap reaches size 1 immediately, and the cost becomes exactly the worker's required wage.
Another important edge case involves workers with identical wage-to-quality ratios. Since they all accept the same pay rate, the optimal solution should simply choose the workers with the smallest qualities. The heap structure handles this automatically because it continuously removes the largest qualities whenever the heap grows too large.
A third critical edge case occurs when a worker has extremely large quality but relatively low ratio. A naive greedy algorithm might incorrectly favor low ratios only, even though a huge quality dramatically increases total cost. This implementation avoids that mistake because it optimizes both components simultaneously: the current ratio and the total quality sum.
Floating-point precision is another subtle issue. The result may contain repeating decimals, so using integer arithmetic would produce incorrect answers. Both implementations use floating-point division for ratios and total cost computation, ensuring sufficient precision for the required tolerance.