Medium

Koko Eating Bananas

044

Given banana piles and h hours, return the minimum integer eating speed needed to finish in time.

EXAMPLES

Example 1

Input
{
  "piles": [
    3,
    6,
    7,
    11
  ],
  "h": 8
}

Output
4

FUNCTION SHAPE

piles: intArrayh: int→int

SOLUTION NOTE

Min template. Search space is [1, max(piles)]. Check: can we finish in <= h hours at speed k?

Reveal reference solution +

pythonREFERENCE

def minEatingSpeed(self, piles: List[int], h: int) -> int:
    def check(k):
        return sum(ceil(p / k) for p in piles) <= h

    left, right = 1, max(piles)
    while left < right:
        mid = left + (right - left) // 2
        if check(mid):
            right = mid
        else:
            left = mid + 1
    return left

TimeO(n log(max(piles)))

SpaceO(1)

Open on LeetCode ↗