Koko must finish every banana pile before the guard returns in h hours. Hours only shrink as her speed grows, so binary search the speeds from 1 to the biggest pile for the slowest one that fits, in O(n log max).
▼The problem
LeetCode 875 (Medium). piles[i] bananas lie in pile i; the guard is back in h hours. Each hour Koko picks one pile and eats up to k bananas from it (if the pile has fewer, she eats them all and waits out the hour). Return the smallest integer speed k that lets her finish every pile within h hours.
Examples (LeetCode's): piles = [3,6,7,11], h = 8 → 4 (the walkthrough example); piles = [30,11,23,4,20], h = 5 → 30 (shown in scene 5: as many hours as piles, so every pile must go in one hour); same piles, h = 6 → 23 (checked, not shown).
The solution
def minEatingSpeed(piles, h):
lo, hi = 1, max(piles)
while lo < hi:
k = (lo + hi) // 2
hours = sum((p + k - 1) // k for p in piles)
if hours <= h:
hi = k
else:
lo = k + 1
return loTranscript
Koko Eating Bananas. Koko has piles of bananas and h hours before the guard returns. Each hour, she eats up to k bananas from one pile. Find the smallest speed k that finishes in time.
Piles of three, six, seven and eleven, with eight hours. At speed four, they take one, two, two and three hours: eight, just in time. Speed three needs ten, so the answer is four.
The naive way tries speed one, two, three and up: up to the biggest pile tries, each summing n piles.
The key: a faster speed never takes more hours. So speeds split into too slow, then fast enough; we want the first that fits. The biggest pile always works: one hour per pile. LeetCode's second example, five piles in five hours, needs exactly thirty. So binary search the speed from one to the biggest pile.
In code, low is one and high is the biggest pile. While they differ, try the middle speed and add up the hours, rounding up. If it fits, it becomes high; if not, low moves past it. Return low.
Let's walk it. Low one, high eleven: try six. Six hours: fits, high is six. Try three: ten hours, too slow, low is four. Try five: eight hours, fits, high is five. Try four: eight, fits, high is four. Low meets high: speed four.
Each check sums n piles, and the search halves the speeds: order n log of the biggest pile time, constant space.
Set the bounds, test the middle, keep the half that fits. That's Koko Eating Bananas.