Problem Statement

You are given an integer array piles where piles[i] is the number of bananas in the ith pile. You are also given an integer h, which represents the number of hours you have to eat all the bananas.

You may decide your bananas-per-hour eating rate of k. Each hour, you may choose a pile of bananas and eat k bananas from that pile. If the pile has less than k bananas, you may finish eating the pile, but you cannot eat from another pile in the same hour.

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

Example 1:

Input: piles = [1,4,3,2], h = 9
Output: 2

Example 2:

Input: piles = [25,10,23,4], h = 4
Output: 25

Thought Process

To find the rate at which Koko can eat bananas, I will have to use trial and error.

Let’s see what happens when I choose to use 1 for this example:

Input: piles = [1,4,3,2], h = 9

First pile:
 numBananas = 1
 bananaEatSpeed = 1
 hoursToEatPile = ceil(1 / 1) = 1
Second pile:
 numBananas = 4
 bananaEatSpeed = 1
 hoursToEatPile = ceil(4 / 1) = 4
Third pile:
 numBananas = 3
 bananaEatSpeed = 1
 hoursToEatPile = ceil(3 / 1) = 3
Fourth pile:
 numBananas = 2
 bananaEatSpeed = 1
 hoursToEatPile = ceil(2 / 1) = 2
---------------------------------------
Total = 10

Since the total hours it will take to eat all of the bananas is greater than the number of hours the bananas need to be eaten in, this rate will not work. We can then try 2 and so on until we find the first banana hourly rate that will consume all of the bananas in less than or equal to the given time h.

Before going further with this implementation, we have to figure out our upper bound for the maximum number of bananas we can eat in 1 hour. Looking back at our example:

Input: piles = [1,4,3,2], h = 9

We can see that we will need to consume at most 4 bananas in 1 hour. This is determined by the largest pile in our list of piles. Knowing this information, we can now set the upper bound for our search as the largest pile size in our list of piles.

The brute force solution to this problem would then look like this:

class Solution:
    def minEatingSpeed(self, piles: List[int], h: int) -> int:
        largestPile = max(piles)
        
        for bananaEatSpeed in range(1, largestPile + 1):
            totalTime = 0
            for pile in piles:
                totalTime += math.ceil(pile / bananaEatSpeed)
            if totalTime <= h:
                return bananaEatSpeed
        
        return largestPile

1. We find the largest pile size to set our upper bound
2. We then try each rate from 1 up until we reach the largest pile size or we find a rate that allows us to finish within the allotted time

This solution works, but binary search gives us the optimal solution in this case. Instead of trying every banana eating rate up until the largest pile, we can instead try fewer rates by splitting our search range in half each time we try a new rate. The time complexity will now go from O(max(piles) * len(piles)) to O(log(max(piles)) * len(piles)), giving us a more efficient solution.

class Solution:
    def minEatingSpeed(self, piles: List[int], h: int) -> int:
        l, r = 1, max(piles)
        minEatSpeed = r
        
        while l <= r:
            bananaEatSpeed = (l + r) // 2
            totalHours = 0
            
            for pile in piles:
                totalHours += math.ceil(pile / bananaEatSpeed)
            
            if totalHours > h:
                l = bananaEatSpeed + 1
            else:
                minEatSpeed = bananaEatSpeed
                r = bananaEatSpeed - 1
                
        return minEatSpeed