ASAPUtils
The signal
“Minimum integer rate that satisfies a deadline” is binary search on the answer. Candidate speed k
has a cheap yes/no test:
hours(k) = sum(ceil(pile / k))
works(k) = hours(k) <= h
Faster speeds never require more time, so feasibility is false then true exactly once.
Bounds
l = 1: zero speed is invalid.r = max(piles): enough to finish every non-empty pile in one hour.
The answer is guaranteed inside that interval.
Optimal solution
int minEatingSpeed(vector<int>& piles, int h) {
int l = 1, r = *max_element(piles.begin(), piles.end());
while (l < r) {
int mid = l + (r - l) / 2;
long long hours = 0;
for (int pile : piles) hours += (pile + mid - 1) / mid;
if (hours <= h) r = mid;
else l = mid + 1;
}
return l;
}
function minEatingSpeed(piles, h) {
let l = 1, r = Math.max(...piles);
while (l < r) {
const mid = l + Math.floor((r - l) / 2);
const hours = piles.reduce(
(sum, pile) => sum + Math.ceil(pile / mid), 0
);
if (hours <= h) r = mid;
else l = mid + 1;
}
return l;
}
Why r = mid
A feasible speed could be the first feasible speed, so it must remain a candidate. A failed speed
and every smaller speed are impossible, so l = mid + 1. The pointers meet at the boundary.
Complexity
Each predicate scans n piles. The speed range has size m = max(piles), so there are O(log m)
checks: O(n log m) time and O(1) extra space.
Traps
- Binary-searching pile indices instead of speeds.
- Starting at zero and dividing by zero.
- Using
floor(pile/speed)rather than ceiling. - Setting
r = mid - 1after a feasible check and accidentally deleting the answer. - Summing hours in a 32-bit C++ integer.
Blank re-solve prompt
State the candidate, predicate, monotonic proof, and both bounds. Only then implement the minimum feasible template.