Koko Eating Bananas

Problem

Distributed batch jobs have a throughput dial: set it too low and jobs miss their deadline, too high and you waste resources. Koko has piles of bananas and h hours before the guards return. She can eat k bananas per hour, finishing a pile in ceil(pile / k) hours. Find the minimum integer k such that she finishes all piles within h hours.

Input: piles = [3, 6, 7, 11], h = 8      → 4
Input: piles = [30, 11, 23, 4, 20], h = 5 → 30
Input: piles = [30, 11, 23, 4, 20], h = 6 → 23

Solution

Approach - binary search on the answer space with a monotonic feasibility check.

The candidate answers are not array indices but eating speeds, and they form a clean range: at speed 1 Koko is slowest, and at speed max(piles) every pile finishes in one hour, so the answer always lies in [1, max(piles)]. The feasibility test can_finish(speed) sums ceil(pile / speed) across all piles - the hours needed at that speed - and returns whether the total is <= h. This test is monotonic: a faster speed never takes more hours, so once a speed works, every larger speed works too. That single yes/no threshold is exactly what binary search needs. Run low, high = 1, max(piles) with while low < high. For each mid, if can_finish(mid) then mid might be the minimum feasible speed, so keep it with high = mid; if it cannot finish, mid is too slow and so is everything below it, so low = mid + 1. The window converges to the smallest speed that passes the check, returned as low. Trace piles=[3,6,7,11], h=8: the search homes in on 4, where ceil gives 1+2+2+3 = 8 hours, just inside the limit, while speed 3 needs 1+2+3+4 = 10.

Edge cases - when h equals the number of piles, each pile must finish in one hour, forcing the answer up to max(piles); the high = mid (never high = mid - 1) and low = mid + 1 (never low = mid) updates are what keep mid in play yet still guarantee progress.

Complexity - O(n log m) time where n is the pile count and m is max(piles) - log m feasibility checks, each O(n); O(1) space.