Capacity to Ship Packages Within D Days
Packages must ship in their given order. Each day the ship loads packages in sequence without exceeding its capacity. Find the minimum capacity that ships everything within days days.
Intuition
This is the same shape as Koko: we cannot compute the capacity directly, but given a candidate we can greedily simulate the loading in one pass and count the days used. Larger capacity never needs more days, so feasibility is monotonic and binary search applies to the capacity itself. The one difference worth noting is the lower bound: capacity must be at least max(weights), because a package heavier than the ship can never be loaded at all.
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.
Approach
Fix the search bounds carefully
The upper bound is sum(weights) — with that capacity everything ships on day one. The lower bound is not 1: it is max(weights), since a single package heavier than the ship's capacity is unshippable no matter how many days are available. Getting this bound wrong is the classic mistake here; starting at 1 wastes probes and, if the feasibility check does not explicitly reject oversized packages, produces wrong answers.
Check a candidate greedily
Given a capacity, walk the packages in order accumulating weight. When the next package would overflow the current day's load, start a new day and put it there. This greedy is optimal because the order is fixed — deferring a package that fits today can never reduce the total number of days. Count the days and compare with the limit.
Binary search on capacity
Probe the midpoint of [max(weights), sum(weights)]. If the greedy fits within days, record it and search lower for a tighter ship. If it needs too many days, search higher. The crossing point is the minimum feasible capacity. O(n log sum) overall.
Solution & live demo
Common pitfalls
Starting lo at 1
lo, hi = 1, sum(weights)
lo, hi = max(weights), sum(weights)
Packages can't be split, so any capacity below the heaviest one makes the problem unsolvable — the greedy check would loop forever or silently miscount. max(weights) is the smallest feasible capacity.
Starting the day counter at 0
used, load = 0, 0
used, load = 1, 0
You're already on day one before loading anything. Counting from 0 reports one fewer day than reality and accepts capacities that miss the deadline by exactly one day.
Resetting load to 0 instead of w when a new day starts
used += 1 load = 0
used += 1 load = w
The package that triggered the new day still has to be shipped — on that new day. Setting load = 0 drops it entirely, so the check reports fewer days than the plan really needs.
Edge cases
The answer is sum(weights) — the top of the search range. Every smaller capacity needs at least two days.
Each package gets its own day, so the answer is max(weights) — the bottom of the range.
It alone forces the lower bound. The search cannot return anything below it, which is exactly why the range starts at max(weights).
The extra days are simply unused; the answer is still max(weights).