Leetcode 875. 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.

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

Note:

  • 1 <= piles.length <= 10^4
  • piles.length <= H <= 10^9
  • 1 <= piles[i] <= 10^9

Difficulty:Medium

Category:

Solution

Koko 吃香蕉的速度是 K , 吃香蕉的最大速度去所有香蕉堆里面的最大值就好,所以有left = 1, right = *max_element(piles.begin(), piles.end()) + 1; 其中最右边的值是可以不选取的,为此我们计算按照这个取得的中间速度计算 kolo能不能在这个中间速度mid内吃完香蕉。如果吃完的时间花费小于限制的时间,那我们就减下吃香蕉的速度,反之就增加吃香蕉的速度。

Time complexity: O(log max_speed), Space complexity: O(1)

class Solution {
 public:
  int minEatingSpeed(vector<int>& piles, int H) {
    // 1) [l, r) -- This is the range for the number of piles
    int left = 1, right = *max_element(piles.begin(), piles.end()) + 1;
    while (left < right) {
      int mid = left + (right - left) / 2, h = 0;
      for (int& pile : piles) h += (pile + mid - 1) / mid;
      h <= H ? right = mid : left = mid + 1;  // Can finished
    }
    return left;
  }
};
By guozetang            Updated: 2020-09-19 13:02:30

results matching ""

    No results matching ""