Koko Eating Bananas

Description

Choose the smallest positive integer eating speed that finishes every banana pile within h hours. Each hour handles only one pile; leftovers in that hour cannot be spent on another pile. Assume h is at least the pile count.

Solution

def min_eating_speed(piles, h):
    left, right = 1, max(piles)
    while left < right:
        middle = (left + right) // 2
        hours = sum((pile + middle - 1) // middle for pile in piles)
        if hours <= h:
            right = middle
        else:
            left = middle + 1
    return left

Examples

Approach

Binary-search speeds between 1 and the largest pile. For each speed, sum ceiling(pile / speed) hours. Feasible speeds form a suffix, so move toward the first feasible speed.