There are some piles of bananas, piles[i] in pile i, and you have h hours to eat them all.
You choose a whole-number speed s (bananas per hour) and keep to it. Each hour, you pick one
pile and eat s bananas from it; if that pile has fewer than s left, you finish it and rest
for the remainder of the hour.
So pile i takes ⌈piles[i] / s⌉ hours (the division rounded up). Return the smallest speed
s that finishes every pile within h hours.
Example 1
- Input
- piles = [4, 9, 6], h = 6
- Output
- 4
Example 2
- Input
- piles = [10, 10], h = 2
- Output
- 10
Constraints
pilesholds 1 to 10⁴ numbers.- Every pile holds 1 to 10⁹ bananas.
piles.length≤h≤ 10⁹, so some speed always works.
Show the pattern
Binary search
If a speed is fast enough, every faster speed is too: the yes/no answer flips exactly once as the speed grows. Binary search on the speed finds where it flips.
See binary search in a visualiserShow the approach
Whether a speed works is a yes/no question that flips once: too slow below some speed, fast
enough from there up. The answer lies between 1 and max(piles): at that speed every pile takes
one hour, and h is at least the number of piles.
Binary search that range, from least = 1 to most = max(piles). For the middle speed, add up
⌈pile / speed⌉ over all the piles. If the total is at most h, the speed works, and so might
a slower one, so it becomes the new most. Otherwise you need to go faster:
least = speed + 1. When least meets most, that is the slowest speed that works.
Time: O(n log m), where m is the biggest pile · Space: O(1)