Capacity To Ship Packages Within D Days (LeetCode 1011)

The problem

Packages on a conveyor belt have weights weights[0], weights[1], … and must be shipped in that order. Each day you load the ship with the next packages, as long as the total weight doesn’t exceed the ship’s capacity. Return the smallest capacity that ships everything within days days.

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

With capacity 15 the days are [1,2,3,4,5], [6,7], [8], [9], [10]. With capacity 14 you need six days.

How to think about it

Start with brute force. Try every capacity from the heaviest package upward and simulate. Each simulation is O(n), and capacities can range up to the total weight, so this is O(n · sum). Another brute force tries every way to cut the belt into days pieces, which is exponential.

Checking one capacity is easy. Given a capacity cap, the best loading is greedy: keep adding the next package to today’s load; when it would overflow, start a new day. Loading less than you can on any day never helps, because the order is fixed. So “can capacity cap finish in days?” is an O(n) check.

The key insight: feasibility is monotonic in capacity, so binary-search it. If capacity cap works, any bigger capacity also works. Across all capacities the answers are no, no, …, yes, yes, and the answer is the first yes. The range is tight: at least max(weights) (the heaviest package must fit) and at most sum(weights) (ship it all in one day).

Which pattern is this? Search on the answer, with a greedy feasibility check. The tell is “minimise the maximum load” or “smallest capacity such that it fits in K groups”. It is the same problem shape as Split Array Largest Sum.

Approach

1. Define ok(cap): start at day 1 with load 0; for each weight, if load + w > cap, move to a new day with load 0; then add w. Return whether the day count is <= days.
2. Set lo = max(weights), hi = sum(weights).
3. While lo < hi: let mid = (lo + hi) // 2. If ok(mid), set hi = mid; else set lo = mid + 1.
4. Return lo.

Solution

def ship_within_days(weights, days):
    def ok(cap):
        d = 1; cur = 0
        for w in weights:
            if cur + w > cap: d += 1; cur = 0   # doesn't fit: start a new day
            cur += w
        return d <= days
    lo, hi = max(weights), sum(weights)         # heaviest package .. everything at once
    while lo < hi:
        mid = (lo + hi) // 2
        if ok(mid): hi = mid                    # works: try smaller
        else: lo = mid + 1
    return lo
# ship_within_days([1,2,3,4,5,6,7,8,9,10], 5) -> 15

Dry run

On weights = [1..10], days = 5, the search starts with lo = 10, hi = 55:

Now lo == hi == 15, so the answer is 15.

Complexity

• Time: O(n log S), where S = sum(weights). There are O(log S) binary-search steps, each with an O(n) greedy check.
• Space: O(1).

Edge cases and pitfalls

• lo must start at max(weights). With a smaller capacity, a single package never fits, and this greedy check would silently put it on its own day as if it fitted, giving a wrong answer.
• days == 1 gives sum(weights); days >= len(weights) gives max(weights).
• Order is fixed. Sorting the weights or using bin packing solves a different problem.
• Off-by-one in the greedy: the new day must start with the current package (cur = 0 then cur += w), not skip it.

Related problems

• Split Array Largest Sum (LeetCode 410): the identical algorithm with different wording.
• Koko Eating Bananas (LeetCode 875): search on the answer with a ceiling-division check.
• Car Pooling (LeetCode 1094): another capacity-feasibility question, answered with a sweep.