Why it works
- A bigger ship never needs more days. So over capacities the checks "in time?" go no, …, no, yes, …, yes, and the answer is the first yes.
- The capacity is at least the heaviest package, or that package never ships, and at most the total weight, which ships everything in one day. So lo starts at max(weights), not at 1.
- To check one capacity, load the packages in order and start a new day only when the next one does not fit. Filling each day as much as possible never takes more days than any other split.
Complexity
Time O(n log s), where n is the number of packages and s their total weight: about log s capacities are tried, and each check walks over all packages. Memory O(1).
nextNow solve it yourself, no hints.
Solve on LeetCode ↗