# 875. Koko Eating Bananas (Medium)

https://leetcode.com/problems/koko-eating-bananas/

Koko loves to eat bananas.  There are `N` piles of bananas, the `i`-th pile has `piles[i]` bananas.  The guards have gone and will come back in `H` hours.

Koko can decide her bananas-per-hour eating speed of `K`.  Each hour, she chooses some pile of bananas, and eats K bananas from that pile.  If the pile has less than `K` bananas, she eats all of them instead, and won't eat any more bananas during this hour.

Koko likes to eat slowly, but still wants to finish eating all the bananas before the guards come back.

Return the minimum integer `K` such that she can eat all the bananas within `H` hours.

Example 1:

```Input: piles = [3,6,7,11], H = 8
Output: 4
```

Example 2:

```Input: piles = [30,11,23,4,20], H = 5
Output: 30
```

Example 3:

```Input: piles = [30,11,23,4,20], H = 6
Output: 23
```

Note:

• `1 <= piles.length <= 10^4`
• `piles.length <= H <= 10^9`
• `1 <= piles[i] <= 10^9`

## Solutions

``````class Solution {

// You can not adopt brute force approach because the size of files is really
// large and the excution will exceeds the time limit.

// Employ binary search from 1 to size of largest pile

public int minEatingSpeed(int[] piles, int H) {
// if size of banana piles is larger than hours, it can not eat up all the bananas
int pileSize = piles.length;

Arrays.sort(piles);

int maxSpeed = piles[pileSize - 1];

// if size of banana piles is as many as hours, the pile of maximum size
// will be the min speed.

if (piles.length == H) {
return maxSpeed;
}

int least = 1;
int most = maxSpeed;

// Work out the threshold speed that happens to finish all the bananas and
// even a little slower will not do.

// binary search is important, refine this solution.
// #TODO
while (most - least > 1) {
int mid = (least + most) / 2;
if (timer(piles, mid, H)) {
most = mid;
} else {
least = mid;
}
}

// the answer could be left or right, check out if the left is the desired one.
if (timer(piles, least, H)) {
return least;
}

return most;
}

public boolean timer(int[] piles, int speed, int H) {
int time = 0;

for (int i = 0; i < piles.length; i++) {
time += (piles[i] + speed - 1) / speed;
}

return time <= H;
}
}
``````