---
# System prepended metadata

title: 875. Koko Eating Bananas
tags: [leetcode]

---

# 875. Koko Eating Bananas
#### Difficulty: Medium
link: https://leetcode.com/problems/koko-eating-bananas/

### 1. Binary Search  
#### $O(n + log\ max(piles))$ runtime, $O(1)$ space

題目關鍵字，找到某個最小值來滿足特定條件，想到Binary search模板。

吃香蕉速度的下限是sum(piles)//h，代表在最理想的情況下(例如只有一個pile)，所有香蕉剛好$h$小時吃完；速度的上限是max(piles)，如此保證可在n小時吃完，n為piles個數。

eat_hours函數計算以速度k吃香蕉需要多少小時。

##### python
```python=
class Solution:
    def minEatingSpeed(self, piles: List[int], h: int) -> int:
        def eat_hours(k):
            return sum([math.ceil(pile / k) for pile in piles])
        
        left, right = max(sum(piles) // h, 1), max(piles)
        
        while left < right:
            mid = left + (right - left) // 2
            if eat_hours(mid) <= h:
                right = mid
            else:
                left = mid + 1
        
        return left
```

###### tags: `leetcode`