Hex.*

LC875 - Koko Eating Bananas

Posted on In
Leetcode: 117/2658 (51+53+13)

Description

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 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

Constraints:

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

Solution

  • According to the meaning of the question, you can know that the slower Koko eats bananas, the more time it takes. On the contrary, the greater the speed, the less time-consuming, which is the monotonicity of the problem;
  • What we’re looking for is speed. Because the question limits Koko to eat only a bunch of bananas within an hour, so the maximum speed is the one with the largest number of these bunches of bananas. The minimum value of the speed is 11, in fact, you can also analyze what the lower bound is. Since the time complexity of binary search is very low, rigorous analysis is not necessary;
  • Or because Koko can only choose a bunch of bananas to eat within an hour, so: the time it takes to eat each bunch of bananas = the number of bananas in this bunch / the number of bananas that Koko eats in an hour. According to the meaning of the question, when / is not divisible, it needs to be rounded up.

Note: When the guessing speed of the “binary search” algorithm is just enough to make Koko eat the bananas within the specified time, you should try a smaller speed to ensure that you can eat the bananas within the specified time.
This is because the question asks about “minimum speed”.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
# O(nlogm) time | O(1) space
class Solution:
    def minEatingSpeed(self, piles: List[int], h: int) -> int:
        l = 1
        r = max(piles)
        
        while l < r:
            mid = l + (r-l)//2
            if self.canFinish(piles, mid, h):
                r = mid
            else:
                l = mid
            
            if l == r-1:
                if self.canFinish(piles, l, h):
                    r = l 
                break
        return r 

    def canFinish(self, piles, speed, hour):
        total = 0
        for pile in piles:
            total+= math.ceil(pile/speed)
            if total > hour:
                return False
        return True
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
# Official Solution: Binary Search (More readable version)
# O(nlogm) time | O(1) space
class Solution:
    def minEatingSpeed(self, piles: List[int], h: int) -> int:  
        # Initalize the left and right boundaries     
        left = 1
        right = max(piles)
        
        while left < right:
            # Get the middle index between left and right boundary indexes.
            # hour_spent stands for the total hour Koko spends.
            middle = (left + right) // 2            
            hour_spent = 0
            
            # Iterate over the piles and calculate hour_spent.
            # We increase the hour_spent by ceil(pile / middle)
            for pile in piles:
                hour_spent += math.ceil(pile / middle)
            
            # Check if middle is a workable speed, and cut the search space by half.
            if hour_spent <= h:
                right = middle
            else:
                left = middle + 1
        
        # Once the left and right boundaries coincide, we find the target value,
        # that is, the minimum workable eating speed.
        return right