Koko Eating Bananas
MediumBinary Search
Koko has n piles of bananas; pile i contains piles[i] bananas. She has h hours before the guards return.
She picks a fixed integer eating speed k (bananas per hour). Each hour she chooses one pile and eats k bananas from it. If that pile has fewer than k bananas left, she eats the rest of it and does nothing else for the remainder of that hour; she never eats from two piles in the same hour. So a pile of size p takes ceil(p / k) hours.
Return the smallest integer k that lets her finish every pile within h hours. Because h >= n, an answer always exists.
Example 1
- Input:
- piles = [4,9,6], h = 6
- Output:
- 4
- Explanation
- At speed 3 the piles take 2 + 3 + 2 = 7 hours, one too many. At speed 4 they take 1 + 3 + 2 = 6 hours, which fits, so 4 is the minimum.
Example 2
- Input:
- piles = [5,5,5], h = 3
- Output:
- 5
- Explanation
- With exactly one hour per pile, each pile must be finished in a single hour, so the speed has to be at least the largest pile, 5.
Example 3
- Input:
- piles = [1000000000], h = 2
- Output:
- 500000000
- Explanation
- One pile and two hours: she needs to eat half of it each hour, a speed of 500000000.
Constraints
1 <= piles.length <= 10^4piles.length <= h <= 10^91 <= piles[i] <= 10^9