Facebook Pixel

Koko Eating Bananas

Medium
LeetCode ↗

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

Explanation

Use the binary search template on Koko's eating speed k. The key is to define a correct can_finish_eating(piles, h, k) function.

For one pile with p bananas, Koko needs ceil(p / k) hours, because she can only work on one pile per hour and a partial final hour still counts as a full hour. Plain division p / k is wrong here: for p = 7 and k = 4, 7 / 4 = 1.75, but the real time is 2 hours.

Sum this value across all piles to get hours_used. If hours_used <= h, speed k is feasible; otherwise it is not. This creates the monotonic behavior needed for binary search: once a speed works, every larger speed also works.

In example 1 (piles = [3,6,7,11], h = 8), this feasibility check behaves as follows.

Implementation

def can_finish_eating(piles, h, k):
    hours_used = 0
    for p in piles:
        hours_used += ceil(float(p) / k)
    return hours_used <= h

def minEatingSpeed(piles, h):
    left, right = 1, 1000000000  # 10^9 max pile size
    ans = -1
    while left <= right:
        mid = (left + right) // 2
        if can_finish_eating(piles, h, mid):
            ans = mid
            right = mid - 1
        else:
            left = mid + 1
    return ans

Ready to land your dream job?

Unlock your dream job with a 5-minute evaluator for a personalized learning plan!

Start Evaluator
Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Tailor Your Study Plan:

How many ways can you arrange the three letters A, B and C?


Recommended Readings

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More