0029 - Koko Eating Bananas

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 eats k bananas from that pile. If the pile has less than k bananas, you may finish eating the pile but you can not 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 Explanation: With an eating rate of 2, you can eat the bananas in 6 hours. With an eating rate of 1, you would need 10 hours to eat all the bananas (which exceeds h=9), thus the minimum eating rate is 2.

Example 2:

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

Output: 25

Solution¶

• min speed 1 banana per hour, res = max speed = max bananas in piles
• binary search, check with mid speed how many hours it takes
• if hours less than h then bring max speed (r) down to mid-1. res=min(res, hours)
• if hours greater than h then increase min speed to mid+1

In [2]:

import math
def minEatingSpeed(piles,h):
    l,r=1,max(piles)    ##eating speed per hour
    res=r
    while l<r:
        mid_speed=(l+r)//2
        hours=0
        for p in piles:
            hours+=math.ceil(float(p)/mid_speed)
        if hours<=h:
            res=min(res,hours)
            r=mid_speed-1
        else:
            l=mid_speed+1
    return res