Approach 1: Binary Search
If Koko can finish eating all the bananas (within
H hours) with an eating speed of
K, she can finish with a larger speed too.
If we let
true if and only if Koko can finish with an eating speed of
K, then there is some
X such that
possible(K) = True if and only if
K >= X.
For example, with
piles = [3, 6, 7, 11] and
H = 8, there is some
X = 4 so that
possible(1) = possible(2) = possible(3) = False, and
possible(4) = possible(5) = ... = True.
We can binary search on the values of
possible(K) to find the first
X such that
True: that will be our answer. Our loop invariant will be that
possible(hi) is always
lo is always less than or equal to the answer. For more information on binary search, please visit [LeetCode Explore - Binary Search].
To find the value of
possible(K), (ie. whether
Koko with an eating speed of
K can eat all bananas in
H hours), we simulate it. For each pile of size
p > 0, we can deduce that Koko finishes it in
Math.ceil(p / K) = ((p-1) // K) + 1 hours, and we add these times across all piles and compare it to
Time Complexity: , where is the number of piles, and is the maximum size of a pile.
Space Complexity: .
Analysis written by: @awice.