DSA problem
Capacity To Ship Packages Within D Days
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.
This is another instance of "binary search the answer" with a monotonic predicate. Let canShip(cap) mean "can we ship all packages within days days using a ship of capacity cap?" If a capacity C works, every capacity larger than C also works — that's the monotonicity that lets you binary search.
The predicate is a greedy simulation: walk through weights left to right, accumulating into the current day's load; whenever adding the next package would exceed cap, start a new day. Count days used and compare to days. This greedy is correct because reordering or splitting is not allowed.
The search range for capacity is [max(weights), sum(weights)]. The lower bound is forced — the ship must fit the heaviest single package. The upper bound trivially works because one day of sum(weights) capacity ships everything. Use the lower-bound binary search shape: lo = max(weights), hi = sum(weights), while lo < hi move hi = mid when canShip(mid) else lo = mid + 1. Time O(n log(sum)) and O(1) space.
Examples
weights = [1,2,3,4,5,6,7,8,9,10], days = 515weights = [3,2,2,4,1,4], days = 36weights = [1,2,3,1,1], days = 43Constraints
- 1 <= days <= weights.length <= 5 * 10^4
- 1 <= weights[i] <= 500
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.