Slowest eating speed
We'll cover the following
Banana piles must all be eaten within h hours, one pile at a time at a fixed speed. Find the smallest speed that works.
Watch it run
Press Play or Step to walk through the example, or change the input and press Run. Each frame says what the algorithm does and why.
lo10
21
32
43
54
65
76
87
98
109
1110
mid1211
1312
1413
1514
1615
1716
1817
1918
2019
2120
2221
2322
hi2423
Speed 12 takes 10 hours. Too slow for 7. Go faster.
piles [24, 9, 17, 4, 20, 13] · limit 7h
1 / 6
The idea
Complexity
| Time | Space | Why |
|---|---|---|
O(n log m) | O(1) | m = the largest pile: log m guesses, each checked in O(n). |
In Python
import math
def min_speed(piles, h):
lo, hi = 1, max(piles)
while lo < hi:
mid = (lo + hi) // 2
hours = sum(math.ceil(p / mid) for p in piles)
if hours <= h: hi = mid # works, try slower
else: lo = mid + 1
return loSummary: say it in the interview
- There is no sorted array here. The sorted thing is the set of possible speeds: if speed s works, every faster speed works too. Binary search the speed, and test each guess with a simple loop.
- Time O(n log m), space O(1). m = the largest pile: log m guesses, each checked in O(n).