Koko has piles of bananas, where piles[i] is the size of pile i, and the guards return in h hours. She picks an eating speed k bananas per hour. Each hour she chooses one pile and eats k bananas from it; if the pile has fewer than k, she finishes it and waits for the rest of that hour. Return the smallest integer k that lets her finish all piles within h hours.
- 1 <= piles.length <= 10^4
- piles.length <= h <= 10^9
- 1 <= piles[i] <= 10^9
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
The brute force tries k = 1, 2, 3, ... and computes the hours each time, which is O(max(piles) * n), far too slow when piles reach 10^9. The key observation: the hours needed is a non-increasing function of k. So "can she finish at speed k?" is false for small k and true from some point on. Binary search over the answer finds that first true speed in O(n log(max)).
Algorithm
- Set
lo = 1andhi = max(piles)(at that speed each pile takes one hour, which is always enough). - While
lo < hi, takemidand computehours = sum of ceil(p / mid)over all piles. - If
hours <= h,midworks: try slower withhi = mid. - Otherwise she is too slow:
lo = mid + 1. - Return
lo.
O(n log M), where M = max(piles)Space: O(1)long. Compute ceil(p / k) as (p + k - 1) / k to stay in integers.class Solution: def minEatingSpeed(self, piles: List[int], h: int) -> int: lo, hi = 1, max(piles) while lo < hi: mid = (lo + hi) // 2 hours = sum((p + mid - 1) // mid for p in piles) # ceil(p / mid) if hours <= h: hi = mid # fast enough, try slower else: lo = mid + 1 # too slow return lo