1011. Capacity To Ship Packages Within D Days

Summary

Return the least weight capacity to ship all the packages within days days.

Example:

Input: weights = [1,2,3,4,5,6,7,8,9,10], days = 5
Output: 15
Explanation: A ship capacity of 15 is the minimum to ship all the packages in 5 days like this:
1st day: 1, 2, 3, 4, 5
2nd day: 6, 7
3rd day: 8
4th day: 9
5th day: 10

Approach

Use binary search on the answer, because increasing the capacity never makes the schedule worse. Let C be the optimal capacity. Any capacity < C fails to ship everything in time, while any capacity >= C succeeds, so the search space is monotonic.

The lower bound is simply the maximum package weight, since a ship must at least hold the heaviest package. The upper bound can be set to 500 * len(weights) per the constraints, which effectively behaves like the sum of all weights.

Function

Initialization

left: max(weights)
right: 500 * len(weights)

While left < right:

mid = (left + right) // 2
if canShip(mid):
    right = mid
else:
    left = mid + 1

Return left.

def canShip(capacity, days):
    required_days = 0
    total = 0
    for w in weights:
        if total + w <= capacity:
            total += w
        else:
            required_days += 1
            total = w

    if total > 0:
        required_days += 1  # Ship the remaining packages.

    return required_days <= days

Complexity

Time Complexity: O(W log R) where W = len(weights) and R is the search range; each binary-search step scans all weights. Space Complexity: O(1).