875. Koko Eating Bananas

2018-08-04

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

code:

we see that the range of piles can be from 1 to 10^9.
so that when when I do the binary search, the low and high pointer in the array will be 1 and (int)1e9.

After that, we find the mid value of low and high pointer and check if it meets the requirements to finish all the banana in time. If it meets the requirements, mid value will be set to high pointer and do the search again, if it doesn’t meet the requirements, the mid value will be set to low pointer + 1 and search.

this way we can determine the time it takes to eat all the piles, and we return low pointer which is the smallest K for which canFinish(K) <= H.

public class Solution {
    public int MinEatingSpeed(int[] piles, int H) {
        int max = (int)1e9;
        int low = 1;
        int high = max;
        while(low < high)
        {
            int mid = (low + high) / 2;
            if(canFinish(piles, mid, H))
                high = mid;
            else
                low = mid + 1;
        }
        return low;
    }
    
    private bool canFinish(int[] piles, int speed, int time)
    {
        int total = 0;
        foreach(var pile in piles)
        {
            total += (pile + speed - 1) / speed;
            if(total > time)
                return false;
        }
        return true;
    }
}