Koko Eating Bananas
There are n piles of bananas and h hours. Each hour Koko picks one pile and eats up to k bananas from it (if the pile is smaller she finishes it and waits). Find the minimum integer speed k that lets her finish every pile within h hours.
- 1 ≤ n ≤ 10^4
- n ≤ h ≤ 10^9
- 1 ≤ piles[i] ≤ 10^9
- "Minimum speed such that…" — an optimisation over the answer
- Feasibility is monotonic: a faster speed never hurts
- Answer range up to 10^9 but each check is O(n)
Sorted input, or any predicate that flips from false to true exactly once over an ordered range, means every comparison can discard half of the candidates. The "search space" need not be an array: it can be the answer itself (a speed, a capacity, a day) as long as feasibility is monotonic in that value.
Binary search on the speed k in [1, max(piles)]. For a candidate speed, the time needed is the sum of ceil(pile / k) over all piles; it is feasible when that total is ≤ h. Feasibility is monotonic in k, so find the smallest feasible value with a lower-bound style search (lo < hi, hi = mid on success, lo = mid + 1 on failure).
- Trying every speed from 1 upward is O(n · M) and hopeless at 10^9; there is no closed form because of the ceilings.