Koko loves to eat bananas. There are n piles of bananas, the ith pile has piles[i] bananas. The guards have gone and will come back in h hours.
Koko can decide her bananas-per-hour eating speed of k. Each hour, she chooses some pile of bananas and eats k bananas from that pile. If the pile has less than k bananas, she eats all of them instead and will not eat any more bananas during this hour.
Koko likes to eat slowly but still wants to finish eating all the bananas before the guards return.
Return the minimum integer k such that she can eat all the bananas within h hours.
Example 1:
Input: piles = [3,6,7,11], h = 8 Output: 4
Example 2:
Input: piles = [30,11,23,4,20], h = 5 Output: 30
Example 3:
Input: piles = [30,11,23,4,20], h = 6 Output: 23
Constraints:
1 <= piles.length <= 10^4piles.length <= h <= 10^91 <= piles[i] <= 10^9
The description was taken from https://leetcode.com/problems/koko-eating-bananas/.
#O(N(Log M)) Time, O(1) Space where N is piles and M is max pile.class Solution: def minEatingSpeed(self, piles: List[int], h: int) -> int: if not piles: return 0 left, right = 1, max(piles) while left < right: bph = (left+right)//2 hours = 0 for pile in piles: hours += math.ceil(pile/bph) if hours <= h: right = bph else: left = bph + 1 return leftThe intuition for this one is rough.
There is no sorted input and we aren't looking for a target value within that input. However, there is a sorted output, and we are looking for a target value within that output.
Those indicate that a binary search may be a good approach.
What we can do is start with a banana-per-hour rate in the middle of our output range. If we see that this rate is too slow and Koko wasn't able to eat all of the bananas, we will try bumping it up. If we see that she was able to eat the bananas, but maybe by a long shot, we will try slowing it down. We will do this until we find the minimum BPH she needs in order for her to eat all the bananas in every pile.
The possible BPH value will fall in between one and the maximum pile of bananas since any rate over the maximum pile will be leftover minutes that will be wasted standing there, and she has to eat at least one banana per hour to eat any.
left, right = 1, max(piles)
Within our search, while the left pointer and right pointers haven't overlapped, that means that we still have BPH values to consider for the minimum, so we will continue the search.
while left < right:
Our search will take a mean BPH between the range of the current left and right pointers.
bph = (left+right)//2
We will also need a running hours counter to see if we undershoot or overshoot the amount of time the guards will be gone for.
hours = 0
Let's continuously go through each pile of bananas and calculate how many hours passed before eating each pile within the current BPH rate, rounding up since any remaining minutes she will stand there burping.
for pile in piles: hours += math.ceil(pile/bph)
If the hours value is less than or equal to the number of hours the guards were gone for, that means that she did eat the bananas, but nearly choked on them from eating so fast then just sat around for the remainder of each hour. We will want to take it down a notch and keep trying to find the minimum BPH where time isn't being wasted.
if hours <= h: right = bph If the hours value is greater than the number of hours the guards were gone for, that means that she didn't even get to eat all of the bananas so we will need to have her put some hustle on it.
else: left = bph + 1 Once our pointers overlap, that means we have exhausted the best search spaces to find the minimum value.
We can return either pointer, but this is the minimum BPH Koko will need to eat in order to finish all of her piles of bananas.
return left