The problem
There are n piles of bananas; pile i has piles[i]. Koko chooses a speed k bananas per hour. Each hour she eats k bananas from one pile — or the whole pile if it has fewer, and then waits for the hour to end.
The guards return in h hours. Return the smallest k that lets her finish every pile in time.
Examples
- Input
piles = [3, 6, 7, 11], h = 8
- Output
4
- Input
piles = [30, 11, 23, 4, 20], h = 5
- Output
30
- Input
piles = [30, 11, 23, 4, 20], h = 6
- Output
23
Constraints
- 1 ≤ piles.length ≤ 10⁴
- piles.length ≤ h ≤ 10⁹
- 1 ≤ piles[i] ≤ 10⁹
The idea
At speed k, a pile of p takes ⌈p ÷ k⌉ hours (rounded up). The total only goes down as k goes up. So there is a line: every speed below the answer is too slow, every speed from it up is fast enough.
Binary search for that line between 1 and the largest pile (at that speed every pile takes one hour, and h is at least the number of piles). Checking one speed costs one pass over the piles.
- Time
- O(n log M) — M is the largest pile
- Space
- O(1)
Solution · every language run against every case
class Solution: def minEatingSpeed(self, piles: List[int], h: int) -> int: def hours(k: int) -> int: return sum((p + k - 1) // k for p in piles) # each pile takes ceil(p / k) hours lo, hi = 1, max(piles) # at max(piles) every pile takes one hour while lo < hi: mid = (lo + hi) // 2 if hours(mid) <= h: hi = mid # fast enough: maybe slower still works else: lo = mid + 1 # too slow return lo