[LeetCode] 875 - Koko Eating Bananas

Problem

給定一個有 n 堆香蕉的陣列 piles (第 i 堆的數量為 piles[i])，以及限時 h 小時，需要找出最少每小時需要吃的香蕉數量，才能在時限內把所有的香蕉吃完。

P.S. 每小時只能吃同一堆香蕉，因此就算那一堆剩餘的香蕉數量小於每小時吃的量，也無法跨堆去吃。

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

Solution

由於 piles 可能的組合太多，而且無法跨堆吃香蕉。因此，我們只能用窮舉的方式來找出答案，但要如何有效率的窮舉，是本題最大的考驗。

簡單整理關於窮舉的資訊：

• 窮舉的範圍是在 [1, max(piles)] (因為題目保證 piles.length() <= h)
• 假設每小時最少要吃的香蕉樹為 k，則 [1, k-1] 的數量都無法在時間內吃完全部香蕉，而 [k, max(piles)] 的數量都可以

有了範圍後，我們就不再是盲目地窮舉，而是搜尋。那講到搜尋，最常見有效、且容易實作的方法就是二分搜尋法 (binary search)。

一般的二分搜尋法，是根據數字大於或小於目標，來調整左界或右界。在此題中，我們則要根據每小時吃的香蕉數量 t，是否能在時限內吃完做調整：

• 可以吃完 → 調整右界為 t (不是 t-1 的原因：不能保證每小時吃 t-1 個也能在時限內吃完，所以只能將右界縮減成確認過的 t 數量)
• 無法吃完 → 調整左界為 t+1

判斷能否在時限內吃完，只需把每堆香蕉的數量 / t (記得要無條件進位喔)，計算所需的小時數，再全部加起來。如果總時數符合時限內，則表示可以吃完。

整數除法 (無條件進位) 比較快速的方法

q = (x + y - 1) / y;
q = 1 + ((x - 1) / y); // if x != 0

Complexity

n 為 piles size

Time complexity: O(nlogn)

• Binary search 總共會搜尋 logn 個數字 * 每個數字的檢查需要掃過整個 array O(n) → O(nlongn)

Space complexity: O(1)

Code

class Solution {
public:
    bool valid(vector<int> &piles, int h, int k) {
        int hr = 0;
        for (int p : piles) hr += (p + k - 1) / k;
        return hr <= h;
    }
    int minEatingSpeed(vector<int>& piles, int h) {
        int l = 1, r = 0;
        for (int p : piles) r = max(p, r);

        while (l < r) {
            int m = (l + r) / 2;
            if (valid(piles, h, m)) r = m;
            else l = m + 1;
        }

        return r;
    }
};

LeetCode Link

https://leetcode.com/problems/koko-eating-bananas/