Capacity To Ship Packages Within D Days
Medium · Binary Search · Array · Binary Search
Problem
Packages on a conveyor belt must be shipped within days days. The i-th package weighs weights[i].
Each day the ship is loaded with packages in the order they appear on the belt, and the total weight loaded on one day may not exceed the ship's capacity. Packages cannot be split or reordered.
Return the minimum ship capacity that allows all packages to be shipped within days days.
Examples
Input: weights = [4,2,7,3,5,1], days = 3 Output: 9
Capacity 9 ships [4,2], [7], [3,5,1]. With capacity 8 the loads are [4,2], [7], [3,5], [1]: four days.
Input: weights = [6,6,6], days = 1 Output: 18
Everything has to go on a single day.
Input: weights = [1,2,3,1,1], days = 4 Output: 3
Capacity 3 ships [1,2], [3], [1,1]: three days. It cannot be smaller than the heaviest package.
Constraints
- 1 <= days <= len(weights) <= 5 · 10^4
- 1 <= weights[i] <= 500
Approaches
- Baseline: try every capacity upward — time O(n · (answer − max)), space O(1)
Follow-up
What if packages could be loaded in any order? Then it becomes bin packing, which is NP-hard: no greedy check is exact any more. The fixed order is what makes a one-pass check possible.
Related problems
Start free on Cariara · Coding problems · System design studio
