67. Capacity to Ship Packages Within D Days
Split the package sequence into daily shipments without changing package order or splitting individual packages. Choose the smallest capacity that allows all packages to arrive within the permitted days.
You may use fewer than the maximum days. Reordering weights to balance shipments is not allowed.
Example 1
Input
weights=[1,2,3,4,5,6,7,8,9,10], days=5
Output
15
Explanation: One valid partition is [1..5], [6,7], [8], [9], [10]; a smaller capacity cannot meet the same deadline.
Example 2
Input
weights=[3,2,2,4,1,4], days=3
Output
6
Explanation: Partitions [3,2], [2,4], [1,4] fit; capacity 5 needs more days.
Example 3
Input
weights=[1,2,3], days=5
Output
3
Explanation: Unused days are allowed; the largest package is still a lower bound.
Constraints
0 <= weights.length <= 1051 <= weights[i] <= 1091 <= days <= 105
Hints
Hint 1
Can increasing capacity ever make a feasible schedule impossible?
Hint 2
Test one capacity by filling each ordered day as far as it can go.
Hint 3
Binary-search the first feasible capacity between maximum weight and total.
Submissions
Your recent submissions for this problem.
Checking sign-in…
Discussion
Ask a question or share an approach. Posts are public; avoid personal information and mark solution spoilers clearly.
No discussion yet. Start the conversation with a question about this problem.
Checking sign-in…
Run your code to check the sample cases, or submit it to check the full validation suite.
First feasible capacity
[2,3,2]
2
5