επιστροφή
> [!META]- Inline Metadata
> [tags:: #career #concepts/programming/algorithms/binary-search ]
> [project group:: Neetcode 150]
> [difficulty:: medium]
> [status:: in progress]
> [link:: ]
> [up:: [[Leetcode MOC]]]
## Problem
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 <= 104`
- `piles.length <= h <= 109`
- `1 <= piles[i] <= 109`
## Solution
### Mine
#### Python
```python
import math
class Solution:
def minEatingSpeed(self, piles: List[int], h: int) -> int:
if len(piles) == h:
return max(piles)
def _hours_to_eat(k):
return sum([math.ceil(i / k) for i in piles])
l, r = 1, max(piles)
sol = r
while l <= r:
m = (l + r) // 2
if _hours_to_eat(m) <= h:
sol = m
r = m - 1
elif _hours_to_eat(m) > h:
l = m + 1
return sol
```
#### Rust
### LC's
## Things I Learned
### Neetcode Video
Brute force solution that can be forced into binary search.
The brute force method is just to iterate through possible k values `[1, .., max(piles)]`, calculating the time to eat all the piles, and stopping at the first one that is <= `h`. This is $O(max(P) * P)$. We can improve it by binary searching the k space to get $O(log(max(P)) * P)$.
Solution is similar to mine:
```python
class Solution:
def minEatingSpeed(self, piles: List[int], h: int) -> int:
l, r = 1, max(piles)
res = r
while l <= r:
k = (l + r) // 2
totalTime = 0
for p in piles:
totalTime += math.ceil(float(p) / k)
if totalTime <= h:
res = k
r = k - 1
else:
l = k + 1
return res
```
## Scratchpad
Because `piles.length` <= `h`, if `piles.length` == `h`, `k` must be the max `piles[i]` since that's the only way to eat all bananas in 1 hour.
For other values of `h`, pick a rate, convert values of `piles` to time taken to eat, sum them, and make sure the number is <= `h`. Minimum `k` will give closest possible value to `h`.
I thought about sorting the list, then starting with the endpoints and binary searching all integers from there for one that would cause `sum([i/k for i in piles])` to equal `h` and couldn't get quite past the conditions:
```python
import math
class Solution:
def minEatingSpeed(self, piles: List[int], h: int) -> int:
if len(piles) == h:
return max(piles)
piles.sort()
def _hours_to_eat(k):
return sum([math.ceil(i / k) for i in piles])
l, r = piles[0], piles[-1]
while l < r:
m = (l + r) // 2
print(f"{l=}\t{m=}\t{r=}")
if _hours_to_eat(m) < h:
r = m
elif _hours_to_eat(m) > h:
l = m
else:
return m
return l
```
The non-binary search brute force method would be like so:
```python
class Solution:
def minEatingSpeed(self, piles: List[int], h: int) -> int:
if len(piles) == h:
return max(piles)
piles.sort()
def _hours_to_eat(k):
return sum([math.ceil(i / k) for i in piles])
solutions = []
for i in range(piles[-1], piles[0], -1):
print(i)
if _hours_to_eat(i) <= h:
solutions.append(i)
return min(solutions)
```
My solution is further up. What got the binary search to work was setting the right or left pointer to m +/- 1 instead of just m.