The slowest rate that clears every queue in time
A worker has several queues of tasks; piles[i] is the number of tasks in queue i. Each
hour the worker picks one queue and completes up to k tasks from it; if the queue has fewer than
k left, the worker finishes it and rests for the rest of that hour. Return the smallest integer rate
k at which every queue is finished within h hours.
Examples
| Input | Output | Why |
|---|---|---|
piles = [3, 6, 7, 11], h = 8 | 4 | At 4 per hour: 1 + 2 + 2 + 3 = 8 hours. At 3: 1 + 2 + 3 + 4 = 10. |
piles = [30, 11, 23, 4, 20], h = 5 | 30 | One hour per queue, so the rate must cover the largest queue. |
piles = [30, 11, 23, 4, 20], h = 6 | 23 |
Constraints
- 1 ≤ piles.length ≤ 10⁴
- piles.length ≤ h ≤ 10⁹
- 1 ≤ piles[i] ≤ 10⁹
Hints
Hint 1
For a given k, how many hours does the work take? Each queue is separate.
Hint 2
Queue i takes ⌈piles[i] / k⌉ hours. The total never increases as k increases. What does that make "the total is at most h"?
Hint 3
A monotone test over k ∈ [1, max(piles)]: false, then true. Search for the first true.
Where people lose marks
- Computing ⌈p / k⌉ with floating-point division, which can round wrongly for large p.
- Summing the hours in a 32-bit integer.
- Starting the search at 0, which divides by zero.
Dry run on [3,6,7,11],8
Read it one frame at a time, the way you would trace the code on paper in an interview. Each frame shows the state after the step it describes.
-
Step 1 / 6lo1hi11
Rates from 1 to max(piles) = 11. The top always works: one hour per queue.
-
Step 2 / 6lo1mid6hi11
At rate 6: 1 + 1 + 2 + 2 = 6 hours, within 8. 6 works, so the answer is 6 or smaller: hi = 6.
-
Step 3 / 6lo1mid3hi6
At rate 3: 1 + 2 + 3 + 4 = 10 hours, over 8. 3 fails, so does everything below it: lo = 4.
-
Step 4 / 6lo4mid5hi6
At rate 5: 1 + 2 + 2 + 3 = 8 hours, within 8. 5 works, so the answer is 5 or smaller: hi = 5.
-
Step 5 / 6lo4mid4hi5
At rate 4: 1 + 2 + 2 + 3 = 8 hours, within 8. 4 works, so the answer is 4 or smaller: hi = 4.
-
Step 6 / 6answer4
lo = hi = 4. Rate 4 needs 8 hours, rate 3 needs 10. The answer is 4.
How to think about it
Turn the question round. Instead of asking for the best rate, ask: at rate k, is h hours enough?
Each queue is worked on its own, and a queue of p tasks takes ⌈p / k⌉ hours, so
hours(k) = Σ ⌈piles[i] / k⌉
in one pass. Raising k can only lower each term, so hours(k) ≤ h is false for small
rates and true from some rate on. The answer is the first rate where it is true.
Bounds: k = 1 is the smallest possible rate, and k = max(piles) always works, since
every queue then takes one hour and h is at least the number of queues. Binary search over
[1, max(piles)] costs O(n log max) instead of trying every rate.
This is the pattern's whole recipe: name the quantity you are minimising, write the feasibility check for a fixed value of it, argue that feasibility is monotone, set bounds where the answer is certainly inside, and search for the first feasible value.
With integers, ⌈p / k⌉ = (p + k − 1) / k. The sum can reach 10⁴ × 10⁹, so accumulate it in 64
bits.
Complexity. Time O(n log max(piles)) · Space O(1)
The solution, in six languages
Each one is compiled and run against the test table before it is published. Java is reviewed by hand.
def min_rate(piles, h):
def hours(k):
return sum((p + k - 1) // k for p in piles) # ceil(p / k) per queue
lo, hi = 1, max(piles) # max(piles) always works
while lo < hi:
mid = (lo + hi) // 2
if hours(mid) <= h:
hi = mid # fast enough; try slower
else:
lo = mid + 1
return lo#include <vector>
#include <algorithm>
long long solve(const std::vector<int>& piles, long long h) {
auto hours = [&](long long k) {
long long t = 0;
for (long long p : piles) t += (p + k - 1) / k; // ceil(p / k)
return t;
};
long long lo = 1, hi = *std::max_element(piles.begin(), piles.end());
while (lo < hi) {
long long mid = lo + (hi - lo) / 2;
if (hours(mid) <= h) hi = mid; // fast enough; try slower
else lo = mid + 1;
}
return lo;
}class Solution {
private long hours(int[] piles, long k) {
long t = 0;
for (int p : piles) t += (p + k - 1) / k; // ceil(p / k)
return t;
}
public int minRate(int[] piles, int h) {
long lo = 1, hi = 0;
for (int p : piles) hi = Math.max(hi, p); // max(piles) always works
while (lo < hi) {
long mid = lo + (hi - lo) / 2;
if (hours(piles, mid) <= h) hi = mid; // fast enough; try slower
else lo = mid + 1;
}
return (int) lo;
}
}function minRate(piles, h) {
const hours = k => piles.reduce((t, p) => t + Math.ceil(p / k), 0);
let lo = 1, hi = Math.max(...piles); // max(piles) always works
while (lo < hi) {
const mid = lo + ((hi - lo) >> 1);
if (hours(mid) <= h) hi = mid; // fast enough; try slower
else lo = mid + 1;
}
return lo;
}fn solve(piles: &[i64], h: i64) -> i64 {
let hours = |k: i64| -> i64 { piles.iter().map(|&p| (p + k - 1) / k).sum() };
let (mut lo, mut hi) = (1i64, *piles.iter().max().unwrap());
while lo < hi {
let mid = lo + (hi - lo) / 2;
if hours(mid) <= h { hi = mid } else { lo = mid + 1 }
}
lo
}solve :: [Int] -> Int -> Int
solve piles h = go 1 (maximum piles)
where
hours k = sum [(p + k - 1) `div` k | p <- piles] -- ceil(p / k) per queue
go lo hi
| lo >= hi = lo
| hours mid <= h = go lo mid
| otherwise = go (mid + 1) hi
where mid = lo + (hi - lo) `div` 2Variants to try
- The worker may split an hour across queues: the answer becomes ⌈sum / h⌉, no search needed.
- Return the rate and the schedule: replay the check at the answer.
Next problems
Smallest ship that clears the backlog in D days
When the answer is a number and "is X enough?" is easy to check, search over answers rather than over data.
Open the problem → Medium20 minThe first day enough adjacent flowers are open
Fix a day and count how many runs of k open flowers it gives, greedily. More days never close a flower, so search the first day that gives m runs.
Open the problem → Medium20 minEarliest time a fleet completes its trips
By time t a vehicle with round-trip time x has finished ⌊t / x⌋ trips. The fleet total never falls as t grows: search the first t that reaches the target.
Open the problem →Write a solution and run it against the real test table.
Keep going
Smallest ship that clears the backlog in D days
When the answer is a number and "is X enough?" is easy to check, search over answers rather than over data.
Open the problem → Medium20 minThe first day enough adjacent flowers are open
Fix a day and count how many runs of k open flowers it gives, greedily. More days never close a flower, so search the first day that gives m runs.
Open the problem → Medium20 minEarliest time a fleet completes its trips
By time t a vehicle with round-trip time x has finished ⌊t / x⌋ trips. The fleet total never falls as t grows: search the first t that reaches the target.
Open the problem → Binary searchThe pattern behind it
Search the answer, not the array: halve a monotone predicate until one candidate is left.
Read the pattern →Preparing for a real process? Quant interview preparation, or book a free 20-minute call.