44. Capacity To Ship Packages Within D Days

読了目安約2分

Binary Search / LeetCode 1011 (Medium) — D 日以内に荷物を運びきる最小の積載量を答えの二分探索で求める。

この章の目次

問題

LeetCode 1011. Capacity To Ship Packages Within D Days（Medium / カテゴリ: Binary Search）

ベルトコンベア上の荷物 weights を、並び順を変えずに船で運びます。 1 日に積めるのは先頭から連続する荷物で、その日の合計重量が船の積載量を超えてはいけません。 days 日以内に全部を運びきれる、最小の積載量を求めます。

考え方

ヒント 1

積載量を 1 つ固定すると、「その積載量で days 日以内に運べるか」は先頭から貪欲に詰めるだけで O(n) で判定できます。この判定は積載量について単調です（大きいほど運びやすい）。

ヒント 2

答えは max(weights) 以上（最も重い荷物 1 個は積める必要がある）、sum(weights) 以下（1 日で全部積める）です。この範囲で「判定が OK になる最小の積載量」を二分探索します。答えの候補を直接探すのではなく判定関数を挟む、答えで二分探索の型です。

Swift 実装のポイント

判定関数は別メソッドに切り出します。荷物を順に足し、積載量を超えたら日数を 1 増やして積み直します。
探索範囲の初期値は weights.max()! と weights.reduce(0, +) で作れます。
「OK になる最小値」を探すので、判定 OK なら high = mid、NG なら low = mid + 1。lower bound と同じ形です。

模範解答

Swift
class Solution {
    func shipWithinDays(_ weights: [Int], _ days: Int) -> Int {
        var low = weights.max()!
        var high = weights.reduce(0, +)
        while low < high {
            let mid = (low + high) / 2
            if canShip(weights, days, mid) {
                high = mid
            } else {
                low = mid + 1
            }
        }
        return low
    }

    private func canShip(_ weights: [Int], _ days: Int, _ capacity: Int) -> Bool {
        var needed = 1
        var current = 0
        for w in weights {
            if current + w > capacity {
                needed += 1
                current = 0
            }
            current += w
        }
        return needed <= days
    }
}

計算量: O(n log S)。S は重さの合計。