koko-eating-bananas.py

"""

875. Koko Eating Bananas
Medium

Share
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

"""

# V0 
# IDEA : BINARY SEARCH
import math
class Solution(object):
    def minEatingSpeed(self, piles, h):
        def help(piles, speed):
            res = 0
            for p in piles:
                # NOTE !!! we use math.ceil here
                res += math.ceil(p / speed)
            return res
        # edge case
        if not piles:
            return 0            
        # binary search
        piles.sort()
        """
        NOTE !!! we init l as 1, r as piles[-1] (or max(piles))
        """
        l = 1
        r = piles[-1]
        while r >= l:
            mid = l + (r - l) // 2
            _hour = help(piles, mid)
            #print ("mid = " + str(mid) + " _hour = " + str(_hour) + " h = " + str(h))
            """
            NOTE !!! the binary search boundary condition is a bit different here:
                -> if _hour <= h (not "<=" !!!)
                    -> we make r = mid -1 
                -> else
                    -> l = mid + 1
            """
            if _hour <= h:
                r = mid - 1
            else:
                l = mid + 1
        ### NOTE : return l, since we minimum integer k (hour) that fit the condition 
        return l

# V1
# IDEA : BINARY SEARCH
# https://leetcode.com/problems/koko-eating-bananas/solution/
class Solution:
    def minEatingSpeed(self, piles, h):  
        # 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:
                # python ceil : https://www.runoob.com/python/func-number-ceil.html
                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

# V1'
# IDEA : BRUTE FORCE
# https://leetcode.com/problems/koko-eating-bananas/solution/
class Solution:
    def minEatingSpeed(self, piles, h):
        #Start at an eating speed of 1.
        speed = 1

        while True:
            # hour_spent stands for the total hour Koko spends with 
            # the given eating speed.
            hour_spent = 0

            # Iterate over the piles and calculate hour_spent.
            # We increase the hour_spent by ceil(pile / speed)
            for pile in piles:
                hour_spent += math.ceil(pile / speed)    

            # Check if Koko can finish all the piles within h hours,
            # If so, return speed. Otherwise, let speed increment by
            # 1 and repeat the previous iteration.                
            if hour_spent <= h:
                return speed
            else:
                speed += 1

# V1''
# https://blog.csdn.net/fuxuemingzhu/article/details/82716042
# IDEA : BINARY SEARCH
# python 3
class Solution:
    def minEatingSpeed(self, piles, H):
        minSpeed, maxSpeed = 1, max(piles)
        while minSpeed <= maxSpeed:
            speed = minSpeed + (maxSpeed - minSpeed) // 2
            hour = 0
            for pile in piles:
                hour += math.ceil(pile / speed)
            if hour <= H:
                maxSpeed = speed - 1
            else:
                minSpeed = speed + 1
        return minSpeed

# V1''''
# https://blog.csdn.net/fuxuemingzhu/article/details/82716042
# IDEA : BINARY SEARCH 
class Solution(object):
    def minEatingSpeed(self, piles, H):
        """
        :type piles: List[int]
        :type H: int
        :rtype: int
        """
        l, r = 1, sum(piles)
        # [l, r)
        while l < r:
            K = l + (r - l) / 2
            curH = 0
            for p in piles:
                curH += p // K + (1 if p % K else 0)
            if curH > H:
                l = K + 1
            else:
                r = K
        return l

# V2 
# Time:  O(nlogr)
# Space: O(1)
class Solution(object):
    def minEatingSpeed(self, piles, H):
        """
        :type piles: List[int]
        :type H: int
        :rtype: int
        """
        def possible(piles, H, K):
            return sum((pile-1)//K+1 for pile in piles) <= H

        left, right = 1, max(piles)
        while left <= right:
            mid = left + (right-left)//2
            if possible(piles, H, mid):
                right = mid-1
            else:
                left = mid+1
        return left