bananas.py

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

 https://leetcode.com/problems/koko-eating-bananas/

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

Brute-force:
time complexity: O(len(piles)*max(piles))
start at 1
    loop through piles checking if chosen pile works
    if it doesn't, pick bananas_per_hour + 1

Bottleneck or unneccessary work:
checking every single number    

possible time complexities:
O(log(len(piles)*max(piles))*len(piles)) Binary Search
O(log(len(piles)*max(piles)) would be possible if we can test a number on all piles in O(1) time
'''

class Solution:
    '''
    Time complexity O(log(len(piles)*max(piles)) * len(piles))
    Space complexity O(1) 
    '''
    def minEatingSpeed(self, piles: List[int], H: int) -> int:
        left = 1
        right = max(piles)
        while left+1 < right:
            mid = (left + right) // 2
        
            if self.consume_piles(mid, piles) > H:
                left = mid
            else:
                right = mid
        
        if self.consume_piles(left, piles) <= H: return left
        else: return right
        
    def consume_piles(self, bananas, piles):
        n = 0
        for banana_pile in piles:
            n += math.ceil(banana_pile/bananas)
        return n