Koko loves to eat bananas. There are n piles of bananas; the i-th pile has piles[i] bananas.
The guards have gone and will come back in h hours. Koko can decide her eating speed k bananas/hour.
Each hour she picks one pile and eats up to k bananas from it. She may eat less than k if the pile has fewer.
Return the minimum integer k such that she can eat all the bananas within h hours.
piles = [3,6,7,11], h = 84piles = [30,11,23,4,20], h = 530piles = [1,1,1,1], h = 41lo=1, hi=max(piles) — the answer space for speed kmid = lo + (hi-lo)/2 and evaluate hours = Σ⌈pile/mid⌉hours ≤ h: mid is feasible — try slower: hi = midhours > h: too slow — need faster: lo = mid + 1lo == hi: found minimum feasible speed — return loThe feasibility function is monotone: if eating speed k lets Koko finish in ≤ h hours, then any speed k' > k is also feasible (faster = fewer hours). So we binary search for the leftmost feasible speed. Each check costs O(n), and the answer space is [1, max(piles)], giving O(n log(max)) overall.
Trying every speed from 1 to the biggest pile is O(n) times max. But if a speed works, every faster speed also works.
That makes the answer space sorted: too slow, then fast enough. Binary search the speed between 1 and the largest pile. For each guess, the hours needed is the sum of each pile divided by k, rounded up.
When a yes stays yes as the value grows, binary search the answer. The check function decides which half to keep.
Run the animation above on your own input, or watch the 1:20 video explanation of Koko Eating Bananas with a dry run and Java code.