Capacity to Ship Packages — DSA Visualizer

Problem

A conveyor belt has packages with weights weights[i]. Each day you load some consecutive packages on a ship with capacity C. You cannot split a package. Find the minimum ship capacity so all packages ship within days days.

Example 1

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

Output: 15

Explanation: Capacity 15 allows shipping in exactly 5 days: [1-5],[6-11],[12],[13],[14-10].

Example 2

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

Output: 6

Example 3

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

Output: 3

Constraints: 1 ≤ weights.length ≤ 500 | 1 ≤ weights[i] ≤ 500 | 1 ≤ days ≤ weights.length

Binary Search Range [lo .. hi]

—

mid

—

lohi

Greedy Loading (capacity = —)

— days needed

D = —

—

State Variables

—

mid (cap)

—

days needed

—

D limit

—

feasible?

—

Step Logic

Select an example above and press Play.

Ready

0 / 0

Select an example above and press Play.

Algorithm

Set lo = max(weights) (ship must hold heaviest), hi = sum(weights) (ship all in 1 day)

Binary search: mid = lo + (hi-lo)/2

Greedily count needed days: pack each weight until overflow, then start new day

If needed ≤ D → feasible, try smaller: hi = mid

Else too tight: lo = mid + 1

When lo == hi → answer is lo

Time

O(n log S)

Space

O(1)

Why Binary Search Works Here

The feasibility function is monotone: if capacity C can ship in ≤ D days, then any C' > C also can. This monotone property means a binary search over capacities converges to the smallest feasible value. The search space [max(w), sum(w)] is tight: below max(w) a single package won't fit; above sum(w) one day suffices.