visual walkthrough
Capacity To Ship Packages Within D Days
MediumBinary Search on Answer
Minimise a capacity subject to a feasibility check.
The idea
A bigger ship never needs more days, so capacities split into "not enough" then "enough".
Binary search between the heaviest package and the total weight. Checking a capacity is a single pass: fill each day until the next package won't fit.
Complexity
| approach | time | space |
|---|---|---|
| Try every capacity | O(n · sum) | O(1) |
| Binary search on capacity | O(n log sum) | O(1) |