Packages must ship in the given order, filling the ship each day up to its capacity. Find the smallest capacity that ships everything within the given number of days.
DSA Animator › DSA Revision › Binary Search › Capacity To Ship Packages Within D Days
Remember: minimize the largest load, so binary search the load. The check is a simple greedy fill. The video solves Capacity To Ship Packages Within D Days (LeetCode 1011, Medium) with the Binary Search on Answer pattern from the Binary Search topic, and you can replay every step in the interactive Capacity To Ship Packages Within D Days animation.
Packages must ship in the given order, filling the ship each day up to its capacity. Find the smallest capacity that ships everything within the given number of days.
For weights 1 to 10 and 5 days, the answer is 15.
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.
The range is 10 to 55. Capacity 32 works, then 21 works, then 15 works. Capacity 12 needs too many days, and so does 14. The range closes at 15, so the answer is 15.
In code, low is the heaviest package and high is the total weight. The check counts days by filling greedily. Keep high at mid when the days fit, otherwise move low past mid. It's O of n log of the total weight.
Remember: minimize the largest load, so binary search the load. The check is a simple greedy fill.