1011.capacity-to-ship-packages-within-d-days.md

1011. Capacity To Ship Packages Within D Days

Linear Search

We can start linear search by iterating the capacity from 1 and find the first capacity that can ship all packages within days.

days = 3
capacity 1, 2, 3, 4, 5    day

1       [1, 2, 3, 4, 5] = 15  X
2       [1, 1, 2, 2, 3] = 9   X
3       [   1, 1, 2, 2] = 6   X
4       [   1, 1, 1, 2] = 5   X
5       [   1, 1, 1, 1] = 4   X
6       [      1, 1, 1] = 3   O <- the least weight capacity
...
10      [         1, 1] = 2   O
...
15      [            1] = 1   O

Binary Search

But we can optimize the solution with some key observations:

As you can see from above example, we can ship all packages within 3 days with the capacity 6, and all capacity >= 6 can ship all packages within 3 days, but all capacity < 6 can't ship all packages within 3 days. As we increase the capacity, the shipped days decreases, and vice versa. If we can ship all packages within D days, then we can definitely ship them with a larger capacity. If we can't ship all packages within D days, then we can't ship them with a smaller capacity. This exhibits the monotonicity characteristic.

capacity 1, 2, 3, 4, 5, 6, ..., 10, ..., 15
feasible X  X  X  X  X  O  ...   O  ...   O
                        ^ // The minimum capacity to ship all packages within D days

And the search space is:

1. Lower bound: The maximum of the weights, we ship each package in exact one day [1][2][3][4][5], and we have to ensure that we can ship every package, so the minimum capacity is at least the maximum weight 5, because each package must fit.
2. Upper bound: The sum of the weights because we can ship all packages [1, 2, 3, 4, 5] = 15 in one day.

We can use binary search to find the minimum capacity: We're looking for the first element that satisfies the condition: shipDays(weights, middle) <= days.

For shipDays(weights, capacity), we can calculate the days needed to ship all packages with the given capacity. We iterate the weights and accumulate the weight greedily before it exceeds the capacity. If it exceeds the capacity, we increment the days and reset the load to the current weight.

class Solution {
    fun shipWithinDays(weights: IntArray, days: Int): Int {
        var max = Int.MIN_VALUE
        var sum = 0
        for (w in weights) {
            max = maxOf(max, w)
            sum += w
        }

        var left = max
        var right = sum
        while (left <= right) {
            val middle = left + (right - left) / 2
            val canShipped = shippedDays(weights, middle) <= days
            // capacity 
            // X X X O O O O O
            if (canShipped) {
                right = middle - 1
            } else {
                left = middle + 1
            }
        }
        return left
    }
}

private fun getShipDays(weights: IntArray, capacity: Int): Int {
    // We count the last group since we don't execute if statement in the last iteration. 
    // 最後一個分組一定不會執行 if 語句，但是還是要算一天。
    // Or check weights = [1], capacity = 6, the answer should be 1, not 0.
    var days = 1 
    var load = 0
    // in the order given by weights as problem description
    for (w in weights) {
        if (load + w > capacity) {
            days++
            load = 0
        }
        load += w
    }
    return days
}

// or equivalently
private fun getShipDays(weights: IntArray, capacity: Int): Int {
    var days = 1
    var load = 0
    for (w in weights) {
        load += w
        if (load > capacity) {
            days++
            load = w
        }
    }
    return days
}

• Time Complexity: O(n log m), where n is the number of weights and m is the sum of the weights.
• Space Complexity: O(1).