Koko Eating Bananas
Binary search the minimum hourly eating speed Koko needs to finish all piles in h hours.
3 min read
binary-search
Problem#
Koko eats k bananas per hour. For each pile, she keeps eating until it’s gone (no spillover within the hour). Return the minimum k such that she finishes all piles within h hours.
Examples#
piles = [3,6,7,11], h = 8→4piles = [30,11,23,4,20], h = 5→30
Constraints#
1 <= piles.length <= n <= h.
Approach#
Binary search on k in [1, max(piles)]. Feasibility: sum(ceil(p / k)) ≤ h.
Solution#
class Solution {public: int minEatingSpeed(vector<int>& piles, int h) { int lo = 1, hi = *max_element(piles.begin(), piles.end()); while (lo < hi) { int mid = lo + (hi - lo) / 2; long long hours = 0; for (int p : piles) hours += (p + mid - 1) / mid; if (hours <= h) hi = mid; else lo = mid + 1; } return lo; }};func minEatingSpeed(piles []int, h int) int { lo, hi := 1, 0 for _, p := range piles { if p > hi { hi = p } } for lo < hi { mid := lo + (hi-lo)/2 hours := 0 for _, p := range piles { hours += (p + mid - 1) / mid } if hours <= h { hi = mid } else { lo = mid + 1 } } return lo}from typing import List
class Solution: def minEatingSpeed(self, piles: List[int], h: int) -> int: lo, hi = 1, max(piles) while lo < hi: mid = lo + (hi - lo) // 2 hours = sum((p + mid - 1) // mid for p in piles) if hours <= h: hi = mid else: lo = mid + 1 return lofunction minEatingSpeed(piles, h) { let lo = 1, hi = Math.max(...piles); while (lo < hi) { const mid = lo + Math.floor((hi - lo) / 2); let hours = 0; for (const p of piles) hours += Math.ceil(p / mid); if (hours <= h) hi = mid; else lo = mid + 1; } return lo;}class Solution { public int minEatingSpeed(int[] piles, int h) { int lo = 1, hi = 0; for (int p : piles) if (p > hi) hi = p; while (lo < hi) { int mid = lo + (hi - lo) / 2; long hours = 0; for (int p : piles) hours += (p + mid - 1) / mid; if (hours <= h) hi = mid; else lo = mid + 1; } return lo; }}function minEatingSpeed(piles: number[], h: number): number { let lo = 1, hi = Math.max(...piles); while (lo < hi) { const mid = lo + Math.floor((hi - lo) / 2); let hours = 0; for (const p of piles) hours += Math.ceil(p / mid); if (hours <= h) hi = mid; else lo = mid + 1; } return lo;}Editorial#
Time-to-finish is monotonically non-increasing in k, so binary search converges to the smallest feasible k. ceil(p/k) = (p + k - 1) / k is the integer-arithmetic ceiling.
Complexity#
- Time: O(n log max(piles)).
- Space: O(1).
Concept revision#
Related#