Capacity To Ship Packages Within D Days

The key idea

The answer is monotonic in capacity: if a capacity c can ship everything within days, so can any capacity larger than c. That lets you binary search the capacity in the range [max(weights), sum(weights)]. For a fixed capacity, a single greedy left-to-right pass — keep loading the current day until the next package would overflow, then start a new day — gives the exact number of days that capacity needs.

Problem

A conveyor belt has packages that must be shipped from one port to another within days days.

The i-th package on the conveyor belt has a weight of weights[i]. Each day, we load the ship with packages on the conveyor belt in the order given by weights. We may not load more weight than the maximum weight capacity of the ship.

Return the least weight capacity of the ship that will result in all the packages on the conveyor belt being shipped within days days.

Constraints

1 <= days <= weights.length <= 5 * 10^4
1 <= weights[i] <= 500

Examples

Input: weights = [1,2,3,4,5,6,7,8,9,10], days = 5 Output: 15

Input: weights = [3,2,2,4,1,4], days = 3 Output: 6

Input: weights = [1,2,3,1,1], days = 4 Output: 3

Complexity

Time: O(n * log(sum)) Space: O(1)

See the full solution

✓Full worked approach
✓Reference code in 5 languages
✓Problem-solving tips
✓Step-by-step animated visualization

410310

Step-by-step visualization

Start free →