Capacity to Ship Packages Within D Days

Capacity to ship packages within d days finds the smallest ship capacity that delivers all packages, in their given order, within days days. Nothing here looks like a search problem at first — but the structure of the answer is what gives it away. Consider what happens as capacity grows. A larger ship never needs more days, and a smaller one never needs fewer. So the predicate "can this capacity finish in time?" is false for small capacities and true for large ones, flipping exactly once: - The feasibility of a capacity is monotonic, which is precisely what binary search requires — even though the input array is not sorted. This is binary search on the answer rather than on the array, and the array's order must be preserved, so sorting it would be wrong. The search bounds come from the problem's own constraints. The lower bound is max(weights), since a ship smaller than the heaviest package can never carry it. The upper bound is sum(weights), which ships everything in a single day. Starting the lower bound at 1 produces an infeasible answer, because the simulation would never fit the heaviest item. The feasibility check is a simple greedy: accumulate weights into the current day until adding the next would exceed capacity, then start a new day. Loading as much as possible each day is optimal, since packages must ship in order and delaying one never helps. When a capacity is feasible, record it and search lower; otherwise search higher. The loop converges on the smallest feasible value. Koko Eating Bananas and Split Array Largest Sum are the same technique with a different feasibility check.

Binary search on the answer again, with the interesting part being the bounds. The capacity can't be below max(weights) — a single package must fit — and never needs to exceed sum(weights), which ships everything in one day. Deriving tight bounds from the problem's physics is half the work.