Capacity To Ship Packages Within D Days

Problem statement

A conveyor has n packages in a fixed order. Package i weighs weights[i]. Each day you load packages from the front, without skipping or reordering, until the next one would exceed the ship’s capacity. Then that day is done.

Find the smallest capacity that still ships every package within days days.

Example:

Input:

weights = [3, 2, 2, 4, 1, 4], days = 3

Expected output:

6

Why: capacity 6 packs as [3, 2] | [2, 4] | [1, 4]. Capacity 5 needs a fourth day ([3, 2] | [2] | [4, 1] | [4]), so 6 is the minimum.

Practice on LeetCode: Capacity To Ship Packages Within D Days

What we are searching for

The answer is not an index in weights. It is a capacity. A package cannot be split, and the order is locked, so two bounds fall out immediately:

• Too small: anything under max(weights) cannot even load the heaviest package.
• Too large: sum(weights) ships everything on day one.

If capacity c finishes on time, every larger capacity does too. If c is too tight, every smaller one is also too tight.

c:        max(w)  …  5  6  7  …  sum(w)
feasible: N       …  N  Y  Y  …  Y

We want the leftmost Y.

Why not try every capacity

Walk c from max(weights) to sum(weights) and simulate the days. Weights go up to 500 and n goes up to 5·10^4, so the sum can be millions. That linear scan will not run.

Binary search over the capacity range is O(n log S), where S is the total weight.

The feasibility check is different from Koko Eating Bananas. Koko sums ceil(pile / k). Here you greedy-pack in order: add the next package to today; if it does not fit, start a new day. You cannot rearrange to fill the ship better. The pattern is the same: search the answer, ask a yes/no question.

Golang Solution

Search c in [max(weights), sum(weights)]. For a candidate mid, ask: does this capacity finish in at most days days? If yes, try smaller. If no, go larger. The loop is the lower-bound form: r = mid when mid works, l = mid + 1 when it does not. l lands on the smallest feasible capacity.

Time: O(n log S) — S is sum(weights)
Space: O(1)

func shipWithinDays(weights []int, days int) int {
    maxWeight, sum := 0, 0

    for _, w := range weights {
        if w > maxWeight {
            maxWeight = w
        }
        sum += w
    }

    l, r := maxWeight, sum

    for l < r {
        mid := l + (r-l)/2

        if feasible(weights, days, mid) {
            r = mid
        } else {
            l = mid + 1
        }
    }

    return l
}

func feasible(weights []int, days int, capacity int) bool {
    daysUsed := 1
    currLoad := 0

    for _, w := range weights {
        if currLoad+w > capacity {
            daysUsed++
            currLoad = w
        } else {
            currLoad += w
        }
    }

    return daysUsed <= days
}

daysUsed starts at 1 because the first package always opens day one. You never need a capacity check on a single package: the search range already starts at max(weights), so currLoad = w always fits.