120. Minimum Shipping Capacity

Why this mechanism works

For a proposed capacity, greedily load the longest possible next prefix each day. Taking fewer packages cannot help later days when all weights are positive and order is fixed. Larger capacities never require more days, creating a monotone feasibility predicate. Bounds are the heaviest package and the total weight.

State and boundaries

used counts days opened and load is the weight assigned to the current day. The outer half-open interval bounds the first feasible capacity.

Protocol

1. Handle empty input.
2. Search capacity from max(weights) through sum(weights).
3. Simulate ordered loading at the midpoint.
4. Open a new day when the next package would overflow.
5. Narrow toward the first capacity using no more than days.

Visualization

weights 3,2,2,4,1,4; days=3
capacity 6: [3,2] | [2,4] | [1,4]
capacity 5 requires more days

Python implementation

def minimum_shipping_capacity(weights, days):
    if not weights:
        return 0
    left, right = max(weights), sum(weights) + 1
    while left < right:
        mid = (left + right) // 2
        used, load = 1, 0
        for weight in weights:
            if load + weight > mid:
                used += 1
                load = 0
            load += weight
        if used <= days:
            right = mid
        else:
            left = mid + 1
    return left

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

L2 minimum_shipping_capacity: if not weights:
weights=[3, 2, 2, 4, 1, 4]; days=3

L4 minimum_shipping_capacity: left, right = max(weights), sum(weights) + 1
weights=[3, 2, 2, 4, 1, 4]; days=3; left=4; right=17

L6 minimum_shipping_capacity: mid = (left + right) // 2
weights=[3, 2, 2, 4, 1, 4]; days=3; left=4; right=17; mid=10

L7 minimum_shipping_capacity: used, load = 1, 0
weights=[3, 2, 2, 4, 1, 4]; days=3; left=4; right=17; mid=10; used=1; load=0

L8 minimum_shipping_capacity: for weight in weights:
weights=[3, 2, 2, 4, 1, 4]; days=3; left=4; right=17; mid=10; used=1; load=0; weight=3

L12 minimum_shipping_capacity: load += weight
weights=[3, 2, 2, 4, 1, 4]; days=3; left=4; right=17; mid=10; used=1; load=3; weight=3

L8 minimum_shipping_capacity: for weight in weights:
weights=[3, 2, 2, 4, 1, 4]; days=3; left=4; right=17; mid=10; used=1; load=3; weight=2

L12 minimum_shipping_capacity: load += weight
weights=[3, 2, 2, 4, 1, 4]; days=3; left=4; right=17; mid=10; used=1; load=5; weight=2

... 62 intermediate state changes omitted ...

L12 minimum_shipping_capacity: load += weight
weights=[3, 2, 2, 4, 1, 4]; days=3; left=6; right=7; mid=6; used=3; load=1; weight=1

L8 minimum_shipping_capacity: for weight in weights:
weights=[3, 2, 2, 4, 1, 4]; days=3; left=6; right=7; mid=6; used=3; load=1; weight=4

L12 minimum_shipping_capacity: load += weight
weights=[3, 2, 2, 4, 1, 4]; days=3; left=6; right=7; mid=6; used=3; load=5; weight=4

L14 minimum_shipping_capacity: right = mid
weights=[3, 2, 2, 4, 1, 4]; days=3; left=6; right=6; mid=6; used=3; load=5; weight=4

L2 minimum_shipping_capacity: if not weights:
weights=[1, 2, 3]; days=1

L4 minimum_shipping_capacity: left, right = max(weights), sum(weights) + 1
weights=[1, 2, 3]; days=1; left=3; right=7

L6 minimum_shipping_capacity: mid = (left + right) // 2
weights=[1, 2, 3]; days=1; left=3; right=7; mid=5

L7 minimum_shipping_capacity: used, load = 1, 0
weights=[1, 2, 3]; days=1; left=3; right=7; mid=5; used=1; load=0

L8 minimum_shipping_capacity: for weight in weights:
weights=[1, 2, 3]; days=1; left=3; right=7; mid=5; used=1; load=0; weight=1

L12 minimum_shipping_capacity: load += weight
weights=[1, 2, 3]; days=1; left=3; right=7; mid=5; used=1; load=1; weight=1

L8 minimum_shipping_capacity: for weight in weights:
weights=[1, 2, 3]; days=1; left=3; right=7; mid=5; used=1; load=1; weight=2

L12 minimum_shipping_capacity: load += weight
weights=[1, 2, 3]; days=1; left=3; right=7; mid=5; used=1; load=3; weight=2

... 10 intermediate state changes omitted ...

L12 minimum_shipping_capacity: load += weight
weights=[1, 2, 3]; days=1; left=6; right=7; mid=6; used=1; load=3; weight=2

L8 minimum_shipping_capacity: for weight in weights:
weights=[1, 2, 3]; days=1; left=6; right=7; mid=6; used=1; load=3; weight=3

L12 minimum_shipping_capacity: load += weight
weights=[1, 2, 3]; days=1; left=6; right=7; mid=6; used=1; load=6; weight=3

L14 minimum_shipping_capacity: right = mid
weights=[1, 2, 3]; days=1; left=6; right=6; mid=6; used=1; load=6; weight=3

Why the solution is correct

For fixed capacity, the greedy first day carries at least as long a prefix as any feasible first day. Repeating on the suffix proves it minimizes required days. This minimum day count is nonincreasing with capacity, so first-true binary search returns the smallest feasible capacity.

Time and space

O(n log(S-M+1)) time for sum S and maximum M, and O(1) auxiliary space.

Common mistakes

Sorting the weights violates shipment order. A lower bound below the heaviest package permits a feasibility routine to place an impossible single package.

Reasoning card

Transfer exercise

Return the actual daily groups for the selected capacity, and distinguish using at most days from requiring exactly days nonempty groups.