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.
weights=[1,2,3,4,5,6,7,8,9,10], days=515weights=[3,2,2,4,1,4], days=36weights=[1,2,3,1,1], days=43lo = max(weights) (ship must hold heaviest), hi = sum(weights) (ship all in 1 day)mid = lo + (hi-lo)/2needed days: pack each weight until overflow, then start new dayneeded ≤ D → feasible, try smaller: hi = midlo = mid + 1lo == hi → answer is lo
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.
Trying every capacity from the heaviest package to the total weight is slow. But a bigger ship never needs more days.
So binary search the capacity between the heaviest package and the total. To check a capacity, load packages greedily, and start a new day when the next one does not fit. If the days needed are within the limit, try smaller.
Minimize the largest load, so binary search the load. The check is a simple greedy fill.
Run the animation above on your own input, or watch the 1:13 video explanation of Capacity To Ship Packages Within D Days with a dry run and Java code.