1011. Capacity to Ship Packages

1011. Capacity to Ship Packages Within D Days

Medium

Description

傳送帶上有 weights 代表的包裹（必須按順序運送），船的載重量為 capacity。每天船會裝載包裹直到無法再裝（不能超重）。求在 days 天內運完所有包裹的最小船載重量。

Example:

Input: weights = [1,2,3,4,5,6,7,8,9,10], days = 5 Output: 15

Intuition#

在答案空間 [max(weights), sum(weights)] 上二分搜尋，找最小的載重量使得能在 days 天內完成。

載重量越大，需要的天數越少 – 具有單調性
最小載重量為 max(weights)（至少要能裝下最重的包裹）
最大載重量為 sum(weights)（一天全部運完）

Approaches#

1: Linear Search#

概念: 從 max(weights) 開始逐一嘗試載重量
時間複雜度: O(n * sum(weights))
空間複雜度: O(1)

Linear Search 程式碼

class Solution {
    fun shipWithinDays(weights: IntArray, days: Int): Int {
        var cap = weights.max()
        while (true) {
            if (canShip(weights, days, cap)) return cap
            cap++
        }
    }

    private fun canShip(weights: IntArray, days: Int, cap: Int): Boolean {
        var daysNeeded = 1
        var currentLoad = 0
        for (w in weights) {
            if (currentLoad + w > cap) {
                daysNeeded++
                currentLoad = 0
            }
            currentLoad += w
        }
        return daysNeeded <= days
    }
}

⭐2: Binary Search on Answer Space#

概念: 在 [max(weights), sum(weights)] 上二分搜尋最小可行的載重量
時間複雜度: O(n * log(sum(weights)))
空間複雜度: O(1)

class Solution {
    fun shipWithinDays(weights: IntArray, days: Int): Int {
        var left = weights.max()
        var right = weights.sum()
        while (left < right) {
            val mid = left + (right - left) / 2
            if (canShip(weights, days, mid)) {
                right = mid
            } else {
                left = mid + 1
            }
        }
        return left
    }

    private fun canShip(weights: IntArray, days: Int, cap: Int): Boolean {
        var daysNeeded = 1
        var currentLoad = 0
        for (w in weights) {
            if (currentLoad + w > cap) {
                daysNeeded++
                currentLoad = 0
            }
            currentLoad += w
        }
        return daysNeeded <= days
    }
}

與 Koko Eating Bananas (#875) 是同一個模式：在答案空間上二分搜尋最小可行值。差別在於 feasibility check 的實作不同。

🔑 Takeaways#

Pattern: Binary Search on Answer（在答案空間上二分搜尋最小可行值）
關鍵技巧: 寫好 canShip() 判斷函式是關鍵。貪心地裝載：盡量裝滿每天的船，裝不下就換一天