https://leetcode.com/problems/koko-eating-bananas/
Koko loves to eat bananas. There are
N piles of bananas, the i-th 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 won't eat any more bananas during this hour.
Koko likes to eat slowly, but still wants to finish eating all the bananas before the guards come back.
Return the minimum integer
K such that she can eat all the bananas within H hours.
coco去吃香蕉，时间最多只有H小时，但这个吃货会享受，她想在用最慢的速度去吃。吃的速度是K，代表一个小时吃多少香蕉。这吃货懒到什么地步？当一个小时以内她就把这堆里边的香蕉吃完了，那她就停下来歇着，等待下一个小时继续吃。求她吃东西的最慢的速度。
二叉搜索的变种题目。因为有个最慢的速度而且是整数。
这个速度的范围一定在1和max(piles)之间，如果大于max(piles)肯定不是最慢速度。然后我们使用二分，计算在某个速度之下吃完的时间是否满足时间H。如果时间比H大，说明她吃的太快了，应该降低速度；反之应该加快速度。
吃每堆香蕉的时间是math.ceil(pile / speed)。
时间复杂度是O(logn)，空间复杂度是O(1)。
- 去找一个值满足某种条件，这种题见得太多了，显然是二分法，之后我整理一下所有的这种题目做一个合辑。
- 那么这里怎么选定初始的lo和hi呢？我们要明确我们找的是吃的速度，那么最低，起码得在吃吧，所以起码lo = 1 or min(piles)，那hi呢？我们注意到note中第二点pile.length <= H，因为我们吃的速度就算再快，一次也只能吃一盘而已，所以无论怎样最少都得pile.length个小时才能吃完，所以hi = max(piles)
public int minEatingSpeed(int[] piles, int H) {
Arrays.sort(piles); // no need sort to get max
long total = 0;
for(int pile : piles) total += pile;
int min = (int)Math.ceil(total/(double)H);
int max = piles[piles.length - 1];
while (min < max){
if (canFinish(piles, min, H)) return min;
if (canFinish(piles, (min + max) / 2, H)) max = (min + max)/2;
else min = (min + max) / 2 + 1;
}
return (int)min;
}
private boolean canFinish(int[] piles, int speed, int target){
long counter = 0;
for (int pile : piles){
counter += Math.ceil(pile / (double)speed);
}
return (int)counter <= target;
}
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
possible(K) be 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.
Algorithm
We can binary search on the values of
possible(K) to find the first X such that possible(X) is True: that will be our answer. Our loop invariant will be that possible(hi) is always True, and 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 Hhours), 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 H.
Time Complexity: , where is the number of piles, and is the maximum size of a pile.
Each hour, Koko chooses some pile of bananas, and eats
Initially, we know that K belongs to [1,
Please note that when
K bananas from that pile. There is a limited range of K's to enable her to eat all the bananas within H hours. We ought to reduce the searching space and to return the minimum valid K, minPile. Binary Search is born for that.Initially, we know that K belongs to [1,
maxPile], (maxPile is the largest element in piles[]). And we follow the pattern of the Binary Search: get the corresponding hourNeeded, compare to target H and reduce the searching range until the minPile and maxPile overlapped.Please note that when
minPile == maxPile we do one more check. If hourNeeded <= H currently, minPile does not change and will be returned. Or else, we increase minPile by 1 and return it. public int minEatingSpeed(int[] piles, int H) {
int minPile = 1, maxPile = Integer.MIN_VALUE;
for (int tmp : piles) {
maxPile = Math.max(maxPile, tmp);
}
while (minPile <= maxPile) {
int hourNeeded = 0;
int i = minPile + (maxPile - minPile) / 2;
for (int tmp : piles) {
if (tmp <= i) {
hourNeeded++;
} else if (tmp % i != 0) {
hourNeeded += tmp / i + 1;
} else {
hourNeeded += tmp / i;
}
}
if (hourNeeded <= H) {
maxPile = i - 1;
}
else {
minPile = i + 1;
}
}
return minPile;
}
(p + m - 1) / m equal to ceil(p / m) (just personal behavior)
public int minEatingSpeed(int[] piles, int H) {
int lo = 1;
int hi = 1_000_000_000;
while (lo < hi) {
int mi = (lo + hi) / 2;
if (!possible(piles, H, mi))
lo = mi + 1;
else
hi = mi;
}
return lo;
}
// Can Koko eat all bananas in H hours with eating speed K?
public boolean possible(int[] piles, int H, int K) {
int time = 0;
for (int p : piles)
time += (p - 1) / K + 1;
return time <= H;
}
