875. Koko Eating Bananas Medium

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

Approach

Input: An integer array piles representing the number of bananas in each pile; an integer h representing the time (in hours) the guard is away.

Output: Return the minimum eating speed k that allows finishing all bananas within h hours.

This problem is a typical Binary Search on Answer problem. Its core lies in: binary searching the minimum speed that satisfies the condition in an answer interval with monotonicity.

Detailed Steps:

1. Determine the Search Interval:

   • The minimum banana eating speed cannot be 0, so the left boundary is left = 1.
   • The maximum speed does not exceed the maximum number of bananas in a pile: right = max(piles) (eating the largest whole pile in one hour).

2. Binary Search:

   • Each time, take the middle speed k = (left + right) // 2.
   • Use this speed k to calculate the total time required to eat all the bananas:
     • For each pile p, the time required is ceil(p / k).
   • If the total time <= h, it means the current speed is feasible. Try to find a slower speed (right = k - 1).
   • Otherwise, it means the speed is too slow. Increase the speed (left = k + 1).

3. Return Result:

   • During the process of satisfying the conditions, record the feasible speed res.
   • Finally, when the binary search ends, res is the minimum eating speed to finish the bananas within h hours.

Implementation

python

import math

class Solution:
    def minEatingSpeed(self, piles: List[int], h: int) -> int:
        # Initialize left and right boundaries:
        # Minimum speed cannot be 0, so start from 1
        # Maximum speed doesn't need to exceed the largest banana pile (at most eat one pile per hour)
        left, right = 1, max(piles)

        res = right  # Initialize the result as the maximum value

        while left <= right:
            # Current test eating speed
            k = left + (right - left) // 2

            totalTime = 0  # Total hours required to finish all bananas at this speed
            for p in piles:
                # Round up for the time spent on each pile, e.g., 5 / 2 = 2.5, requires 3 hours
                totalTime += math.ceil(p / k)

            if totalTime <= h:
                # Current speed k allows eating all bananas within h hours, try slower speed
                res = k
                right = k - 1
            else:
                # Current speed is too slow to finish, try faster speed
                left = k + 1

        return res  # Return the minimum eating speed

javascript

const minEatingSpeed = function(piles, h) {
    // Initialize search interval: minimum speed is 1
    let left = 1;
    let right = Math.max(...piles); // Maximum speed is the max value in the piles

    let res = right; // Initialize result to the max speed

    while (left <= right) {
        // Current testing speed k
        let k = left + Math.floor((right - left) / 2);

        let totalTime = 0; // Total time to eat bananas at current speed

        // Iterate through each pile, calculate the time needed for each (rounded up)
        for (let p of piles) {
            totalTime += Math.ceil(p / k);
        }

        if (totalTime <= h) {
            // Speed allows finishing within h hours, record speed
            res = k;
            // Try slower speed
            right = k - 1;
        } else {
            // Processing is too slow, increase the speed
            left = k + 1;
        }
    }

    return res; // Return the minimum valid speed
};

Complexity Analysis

• Time Complexity: O(n log M), where M is the maximum value in piles and n is the length of piles
• Space Complexity: O(1)

Links

875. Koko Eating Bananas (English)

875. 爱吃香蕉的珂珂 (Chinese)