1011. Capacity To Ship Packages Within D Days - Medium

前往題目

想法

• Binary Search，通常找min或max的都可以先往這方面想

思路

1. 算出所有貨物總和，這樣就知道最大需要多重的運輸能力
2. 從一半的可能重量開始看是否可以在期限內運送
3. 如果可以就嘗試減少重量再看看是否可以
4. 如果不行就嘗試增加重量

Code

網友解答

class Solution {
    public int shipWithinDays(int[] weights, int days) {
        int sum = 0; // Sum of the weights of the cargos
        for (int cargo : weights) {
            sum += cargo;
        }

        int min = 1, max = sum; // At least 1 capacity per day, max is the total sum which can ship the cargos at once
        int res = 0; // Final result

        // Binary search for the min capacity within "days" timeframe
        while (min <= max) {
            int mid = min + (max - min) / 2; // Current capacity

            int weightSum = 0; // Total sum of current weights

            boolean canLiftOneMinCargo = true; // Flag to indicate the current capacity is not possible to lift the min. weight cargo
            
            int k = 1; // Days required with current capacity
            
            // Check required days if ship with the current capacity
            for (int i = 0; i < weights.length; ++i) {

                // Capacity is not possible to ship even 1 cargo
                if (mid < weights[i]) {
                    canLiftOneMinCargo = false;
                    break; // This capacity is impossible
                }

                weightSum += weights[i];

                // Exceed one shipment capacity
                if (weightSum > mid) {
                    // Start another day
                    weightSum = 0;
                    ++k; // Day + 1
                    --i; // Ship current cargo in tomorrow
                }
            }

            // This capacity is valid
            if (canLiftOneMinCargo && k <= days) {
                res = mid; // Assign current capacity
                max = mid - 1; // See if we can do it in less capacity
            } else { // Invalid, should increase the capacity
                min = mid + 1;
            }
        }
        return res;
    }
}