[LeetCode] Koko Eating Bananas

Problem: Koko loves to eat bananas. There are n piles of bananas, the ith 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 will not eat any more bananas during this hour.

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

Return the minimum integer k such that she can eat all the bananas within h hours.

Example:

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

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

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

Constraints:

• 1 <= piles.length <= 104
• piles.length <= h <= 109
• 1 <= piles[i] <= 109

Approach: This is again a binary search problem but how? Where is our sorted array? Sorted array is speed of eating banana which could be in range 1, 2, 3, ...., Max(piles). Right.

Now what to compare with mid? This is easy, we need to see if with mid speed, all the bananas can be eaten or not. If all the bananas can't be eaten then that means we need to increase the speed, right. This means start will become mid + 1;

If it can be eaten then with speed mid that means we just need to check if there is a speed which is less than mid with which all the bananas can still be eaten withn h hours. Remember we need to find the minimum speed with which all the bananas can be eaten within h hours so that means we need to go left side so end will become mid.

That's all!

Implementation in C#:

    public int MinEatingSpeed(int[] piles, int h)

    {

        int start = 1;

        int end = Enumerable.Max(piles);

        while (start < end)

        {

            int mid = start + (end - start) / 2;

            if (this.BananaCanBeEaten(piles, mid, h))

            {

                end = mid;

            }

            else

            {

                start  = mid + 1;

            }

        }

        return start;

    }

    private bool BananaCanBeEaten(int[] piles, int speed, int h)

    {

        long hours = 0;

        foreach(int pile in piles)

        {

            hours += (pile / speed);

            if (pile % speed != 0)

            {

                ++hours;

            }

        }

        return hours <= h;

    }

Complexity:  O(n + nlog(max(pile)))