Koko eating bananas: slowest speed that finishes in time

Koko has n piles of bananas, the i-th with piles[i] bananas, and h hours before the guards return. She picks a constant speed k bananas per hour. Each hour she chooses one pile and eats k bananas from it; if the pile has fewer, she finishes it and eats nothing more that hour. Return the smallest integer k that lets her finish every pile within h hours.

Interface

Unless you agree on a different interface with the interviewer, assume:

• min_eating_speed(piles: list[int], h: int) -> int.

Example

min_eating_speed([3, 6, 7, 11], 8)          ->  4     # 1 + 2 + 2 + 3 = 8 hours; k = 3 needs 10
min_eating_speed([30, 11, 23, 4, 20], 5)    ->  30    # one hour per pile, so k = max(piles)
min_eating_speed([30, 11, 23, 4, 20], 6)    ->  23
min_eating_speed([1000000000], 2)           ->  500000000

Constraints

• 1 <= len(piles) <= h <= 10^9.
• 1 <= piles[i] <= 10^9.

Clarifying questions

• Is h always at least the number of piles? (If not, no speed works.)
• Can she split an hour between two piles? (No.)
• Must k be an integer?
• Can a pile be empty?

What a strong answer covers

• The hours needed at speed k are sum(ceil(p / k)), computed with integer arithmetic (p + k - 1) // k, never floats.
• Monotonic: if k works, every larger speed works. So binary search the smallest working k in [1, max(piles)].
• O(n log max(piles)) time, O(1) space; a tighter lower bound ceil(sum / h) as an optimisation.
• The binary search written carefully (lo < hi, hi = mid on success, lo = mid + 1 otherwise) and overflow-safe sums in fixed-width languages.
• Tests: one pile, h equal to the number of piles, very large h, very large piles.

Follow-ups

• What if h is smaller than the number of piles?
• She may eat from two piles in one hour if she finishes the first.
• Return the speed as a real number with a given precision.