Capacity To Ship Packages Within D Days
Solve and submit on LeetCode to build your LeetCode profile. Use the hints here when you need guidance.
Problem
Packages must be shipped in the given order, and each day the ship is loaded with a consecutive run of packages whose total weight does not exceed its capacity. Find the lowest ship capacity that gets every package delivered within the given number of days.
Examples
Constraints
- • 1 <= days <= weights.length <= 5 * 10^4
- • 1 <= weights[i] <= 500
Hints & approach
Hint 1
The capacity can never be smaller than the heaviest package, nor needs to exceed the total weight.
Hint 2
Given a capacity, you can greedily count how many days shipping takes.
Hint 3
More capacity never needs more days, so binary search between the two bounds.
Approachtry the hints first
Binary search the capacity between max(weights) and sum(weights). To test a capacity, walk the packages greedily: keep adding to today's load, and start a new day when the next package would overflow. If the day count is within the limit, the capacity is feasible and you try smaller (hi = mid); otherwise go larger (lo = mid + 1). Feasibility is monotonic, so the search finds the smallest working capacity.
Time O(n log S), S = sum of weights · Space O(1)
