koko_eating_bananas
1from math import ceil 2 3 4# @leet start 5class Solution: 6 def minEatingSpeed(self, piles: list[int], h: int) -> int: 7 """ 8 This problem asks to find the rate `k` it takes for Koko to eat 9 all the piles of bananas in `h` hours, given once she finishes a pile 10 she can't move onto another pile, and there's no travel time. 11 12 The naive solution involves iterating from 1 to the largest pile and 13 checking if koko can eat all the bananas. 14 This solution is $O(mn)$ time, since for each pile $n$, you have to check 15 $m$ rates, from 1 to m. 16 17 We can optimize this: there's a way to answer this problem in $O(n * \log{}m)$ time. 18 This can be done by using binary search. 19 If our rate `k` can eat the bananas in time, then `k+1` can as well, but is worse. 20 Likewise, there's not a guarantee that `k-1` can solve the problem. 21 So if too many bananas are eaten too quickly, we can reduce `k`. 22 If not enough bananas are eaten, we can increase `k`. 23 24 The solution has a trick though, instead of normal binary search, if koko 25 can eat all the bananas, we set right = mid and continue recursing. 26 Otherwise, we set left = mid + 1. 27 28 When left == right, we've found the minimum rate. We can either return 29 left or right at that point. 30 """ 31 left = 1 32 right = max(piles) 33 34 while left < right: 35 mid = (left + right) // 2 36 hours_spent = sum(ceil(pile / mid) for pile in piles) 37 38 if hours_spent <= h: 39 right = mid 40 else: 41 left = mid + 1 42 43 return right 44 45 46# @leet end 47 48 49def test(): 50 assert 2 + 2 == 4
class
Solution:
6class Solution: 7 def minEatingSpeed(self, piles: list[int], h: int) -> int: 8 """ 9 This problem asks to find the rate `k` it takes for Koko to eat 10 all the piles of bananas in `h` hours, given once she finishes a pile 11 she can't move onto another pile, and there's no travel time. 12 13 The naive solution involves iterating from 1 to the largest pile and 14 checking if koko can eat all the bananas. 15 This solution is $O(mn)$ time, since for each pile $n$, you have to check 16 $m$ rates, from 1 to m. 17 18 We can optimize this: there's a way to answer this problem in $O(n * \log{}m)$ time. 19 This can be done by using binary search. 20 If our rate `k` can eat the bananas in time, then `k+1` can as well, but is worse. 21 Likewise, there's not a guarantee that `k-1` can solve the problem. 22 So if too many bananas are eaten too quickly, we can reduce `k`. 23 If not enough bananas are eaten, we can increase `k`. 24 25 The solution has a trick though, instead of normal binary search, if koko 26 can eat all the bananas, we set right = mid and continue recursing. 27 Otherwise, we set left = mid + 1. 28 29 When left == right, we've found the minimum rate. We can either return 30 left or right at that point. 31 """ 32 left = 1 33 right = max(piles) 34 35 while left < right: 36 mid = (left + right) // 2 37 hours_spent = sum(ceil(pile / mid) for pile in piles) 38 39 if hours_spent <= h: 40 right = mid 41 else: 42 left = mid + 1 43 44 return right
def
minEatingSpeed(self, piles: list[int], h: int) -> int:
7 def minEatingSpeed(self, piles: list[int], h: int) -> int: 8 """ 9 This problem asks to find the rate `k` it takes for Koko to eat 10 all the piles of bananas in `h` hours, given once she finishes a pile 11 she can't move onto another pile, and there's no travel time. 12 13 The naive solution involves iterating from 1 to the largest pile and 14 checking if koko can eat all the bananas. 15 This solution is $O(mn)$ time, since for each pile $n$, you have to check 16 $m$ rates, from 1 to m. 17 18 We can optimize this: there's a way to answer this problem in $O(n * \log{}m)$ time. 19 This can be done by using binary search. 20 If our rate `k` can eat the bananas in time, then `k+1` can as well, but is worse. 21 Likewise, there's not a guarantee that `k-1` can solve the problem. 22 So if too many bananas are eaten too quickly, we can reduce `k`. 23 If not enough bananas are eaten, we can increase `k`. 24 25 The solution has a trick though, instead of normal binary search, if koko 26 can eat all the bananas, we set right = mid and continue recursing. 27 Otherwise, we set left = mid + 1. 28 29 When left == right, we've found the minimum rate. We can either return 30 left or right at that point. 31 """ 32 left = 1 33 right = max(piles) 34 35 while left < right: 36 mid = (left + right) // 2 37 hours_spent = sum(ceil(pile / mid) for pile in piles) 38 39 if hours_spent <= h: 40 right = mid 41 else: 42 left = mid + 1 43 44 return right
This problem asks to find the rate k it takes for Koko to eat
all the piles of bananas in h hours, given once she finishes a pile
she can't move onto another pile, and there's no travel time.
The naive solution involves iterating from 1 to the largest pile and checking if koko can eat all the bananas. This solution is $O(mn)$ time, since for each pile $n$, you have to check $m$ rates, from 1 to m.
We can optimize this: there's a way to answer this problem in $O(n * \log{}m)$ time.
This can be done by using binary search.
If our rate k can eat the bananas in time, then k+1 can as well, but is worse.
Likewise, there's not a guarantee that k-1 can solve the problem.
So if too many bananas are eaten too quickly, we can reduce k.
If not enough bananas are eaten, we can increase k.
The solution has a trick though, instead of normal binary search, if koko can eat all the bananas, we set right = mid and continue recursing. Otherwise, we set left = mid + 1.
When left == right, we've found the minimum rate. We can either return left or right at that point.
def
test():