Eat Bananas in K Hours

Description

You are given a list of integers piles and an integer k. piles[i] represents the number of bananas on pile i. On each hour, you can choose any pile and eat r number of bananas in that pile. If you pick a pile with fewer than r bananas, it still takes an hour to eat the pile.

Return the minimum r required such that you can eat all the bananas in less than or equal to k hours.

Constraints:

• n ≤ 100,000 where n is the length of piles
• n ≤ k

Example 1

Input

piles = [6, 4, 3]
k = 5

Output

3

Explanation

At r = 3 bananas per hour, we can eat the first pile in 2 hours, eat the second in 2 hours, and eat the last pile in 1 hour.

---

Intuition

binary search

• l: at least eat 1 banana
• r: the maximum number of bananas in a pile

Implementation

import java.util.*;

class Solution {
    public int solve(int[] piles, int k) {
        int n = piles.length;
        int l = 1, r = Integer.MIN_VALUE;
        for (int pile : piles) {
            r = Math.max(pile, r);
        }

        while (l < r) {
            int mid = l + r >> 1;
            if (canEat(mid, piles, k)) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }

    private boolean canEat(int r, int[] piles, int k) {
        int hours = 0;
        for (int pile : piles) {
            hours += Math.ceil((float) pile / r);
        }
        return hours <= k;
    }
}

Time Complexity

• Time: O(nlogn)
• Space: O(1)