[leetcode #875] Koko Eating Bananas

Problem

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 <= 10⁴
・ piles.length <= h <= 10⁹
・ 1 <= piles[i] <= 10⁹

Idea

푸는 방향은 맞았는데 index 조정을 잘 못 해서 풀지 못 했다 🥲

바나나 더미 중 가장 많은 더미가 쌓인 곳을 찾아서 해당 개수를 right boundary로, 1을 left boundary로 잡고 binary search로 찾으면 된다. 중간값을 기준으로 각 더미마다 걸리는 시간을 구한다. 걸리는 시간 전체가 주어진 시간 h보다 작거나 같다면 right boundary를 중간값으로 잡고, 크다면 left boundary를 중간값에 1을 더한 것으로 설정한다.

두 boundary가 똑같을 경우 시간당 먹는 바나나 수의 최소값이 구해진 것이므로 해당값을 리턴하면 된다.

Solution

class Solution {
    public int minEatingSpeed(int[] piles, int h) {
        // Initalize the left and right boundaries 
        int left = 1, right = 1;
        for (int pile : piles) {
            right = Math.max(right, pile);
        }

        while (left < right) {
            // Get the middle index between left and right boundary indexes.
            // hourSpent stands for the total hour Koko spends.
            int middle = (left + right) / 2;
            int hourSpent = 0;

            // Iterate over the piles and calculate hourSpent.
            // We increase the hourSpent by ceil(pile / middle)
            for (int pile : piles) {
                hourSpent += Math.ceil((double) pile / middle);
            }

            // Check if middle is a workable speed, and cut the search space by half.
            if (hourSpent <= 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;
    }
}

Reference

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