Leetcode 875. 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

Approach 1: Binary Search

Intuition

Call an eating speed K a candidate if Koko can finish eating all the bananas within H hours while having an eating speed of K. This is motivated by the fact that we want to find the smallest candidate.

If K is a candidate, then any speed larger than K is also a candidate, as a faster speed would make her finish eating all bananas in at most the same amount of time.

Let X be the answer desired - the smallest candidate. Then every value less than X is not a candidate (because X is chosen as the smallest), and every value larger than X is a candidate (because of the reasoning above).

Algorithm

Say possible(K) is true if and only if K is a candidate. If we were to write out possible(0), possible(1), ..., it would look like [False, False, ..., False, True, True, ...]: with only the first X values being False, and the rest True.

We can binary search on these values to find the first X such that possible(X) is True: that will be our answer. Our loop invariant will be that possible(hi) is always True, and lo is always less than or equal to the answer. For more information on binary search, please visit [LeetCode Explore - Binary Search].

To find the value of possible(K), (ie. whether Koko with an eating speed of K can eat all bananas in H hours), we simulate it. For each pile of size p > 0, we can deduce that Koko finishes it in ((p-1) // K) + 1 hours, and we add these times across all piles and compare it to H.

Code (Java):

class Solution {
    public int minEatingSpeed(int[] piles, int H) {
        int lo = 1;
        int hi = 1000000000;
        
        while (lo + 1 < hi) {
            int mid = lo + (hi - lo) / 2;
            
            if (canFinish(mid, piles, H)) {
                hi = mid;
            } else {
                lo = mid + 1;
            }
        }
        
        if (canFinish(lo, piles, H)) {
            return lo;
        } else {
            return hi;
        }
    }
    
    private boolean canFinish(int K, int[] piles, int H) {
        int time = 0;
        for (int cBananas : piles) {
            time += (cBananas - 1) / K + 1;
        }
        
        return time <= H;
    }
}

Another better solution with better low and high boundaries

class Solution {
    public int minEatingSpeed(int[] piles, int H) {
        Arrays.sort(piles);
        long total = 0;
        for(int pile : piles) total += pile;
        int min = (int)Math.ceil(total/(double)H);
        int max = piles[piles.length - 1];
        while (min < max){
            if (canFinish(piles, min, H)) return min;
            if (canFinish(piles, (min + max) / 2, H)) max = (min + max)/2;
            else min = (min + max) / 2 + 1;
        }
        return (int)min;
    }
    
    
    private boolean canFinish(int[] piles, int speed, int target){
        long counter = 0;
        for (int pile : piles){
            counter += Math.ceil(pile / (double)speed);
        }
        return (int)counter <= target;
    }
}