Koko Eating Bananas

Each hour, Koko eats up to k bananas from one pile. A smaller pile is finished early, and she waits out the hour. Find the smallest k that finishes every pile within h hours.

For piles = [3, 6, 7, 11] and h = 8, the answer is 4. At speed 4 the piles take 1 + 2 + 2 + 3 = 8 hours.

A pile of p takes p / k hours, rounded up.

A faster speed never takes more hours. So the speeds from 1 to the biggest pile line up as too slow, then fast enough from some speed on.

That makes them searchable. Try the middle speed. If it's fast enough, the answer is it or slower. If not, the answer is faster.

The piles don't need to be sorted. The speeds are what's in order.

Start with left = 1 and right = max(piles). The biggest pile's speed finishes each pile in an hour, so it always works when h is at least the number of piles.

while left < right:
    mid = (left + right) // 2
    hours = sum((p + mid - 1) // mid for p in piles)
    if hours <= h:
        right = mid
    else:
        left = mid + 1
return left

(p + mid - 1) // mid is p / mid rounded up, in whole numbers.

Run it on piles = [3, 6, 7, 11] with h = 8.

Speeds 1 to 11 are in play. Speed 6 takes 6 hours, so right = 6. Speed 3 takes 10, too slow, so left = 4. Speed 5 takes 8, so right = 5. Speed 4 also takes 8, so right = 4. Now left = right = 4.

The answer, 4, isn't a pile size. It can be any speed.

• Round up. p // k undercounts any pile that doesn't divide evenly.
• Start left at 1. Speed 0 never finishes.
• Keep mid when it works: right = mid, not mid - 1.
• When h equals the number of piles, each pile gets one hour, so the answer is the biggest pile.
• In languages with fixed-size integers, the hour total can overflow. Use a wide type.

Each try adds up all n piles: O(n). The speed range halves each try, so there are O(log m) tries, where m is the biggest pile.

That's O(n log m) time and O(1) extra space.