Koko Eating Bananas

Problem

A monkey is given n piles of bananas, piles[i] bananas in the i-th pile, and a window of h hours to eat all of them. She eats at a fixed speed of k bananas per hour: each hour she picks one pile and eats k bananas from it, or the whole pile if fewer than k remain, in which case the rest of that hour is wasted. She never works on two piles in the same hour.

Return the smallest integer speed k at which every pile is gone within h hours.

• Between 1 and 20,000 piles, each holding between 1 and 2,000,000,000 bananas.
• h is at least the number of piles (so a solution always exists) and at most 2,000,000,000.

Examples

• piles = [5, 9, 14, 20], h = 7 → 9. At speed 9 the piles take 1 + 1 + 2 + 3 = 7 hours; at speed 8 they take 1 + 2 + 2 + 3 = 8, one too many.
• piles = [12, 8, 25, 16], h = 4 → 25. With exactly one hour per pile she must eat the biggest pile in one sitting.
• piles = [12, 8, 25, 16], h = 5 → 16. One spare hour lets her split only the largest pile; at speed 15 the pile of 16 would also need two hours.

Hints

1. Given a candidate speed k, how quickly can you tell whether it is fast enough?
2. If speed k works, does every speed larger than k also work? What does that monotonic property let you do?
3. Binary search over the speed, using the "total hours at speed k" function as the predicate. The answer is between 1 and the largest pile.