Koko Eating Bananas
Part of Practice: Search Templates
Koko has piles of bananas, where piles[i] is the size of pile i, and h hours before the guards return. Each hour she picks one pile and eats up to k bananas from it; if the pile has fewer than k left, she finishes it and still uses the whole hour. Return the smallest whole-number speed k that lets her finish every pile within h hours.
Key constraints: the number of piles never exceeds h (so a solution always exists), piles can be up to 10^9 bananas, and there can be up to 10^4 piles — so trying every possible speed one by one is too slow.
Examples
- Input:
- piles = [3, 6, 7, 11], h = 8
- Output:
- 4
At speed 4 the piles take ceil(3/4) + ceil(6/4) + ceil(7/4) + ceil(11/4) = 1 + 2 + 2 + 3 = 8 hours, exactly the budget. Speed 3 would take 9 hours, which is too many.
- Input:
- piles = [30, 11, 23, 4, 20], h = 5
- Output:
- 30
With 5 piles and 5 hours, each pile must be finished in a single hour, so k must be at least the largest pile.
- Input:
- piles = [30, 11, 23, 4, 20], h = 6
- Output:
- 23
One extra hour lets the 30-pile be split across two hours; every other pile still fits in one hour at speed 23.
Hints
One at a time — struggle first, peek second.
Your thinking space — verify on LeetCode, then mark it.