591. Capacity To Ship Packages Within D Days
A conveyor belt feeds packages onto a ship in the given order — you may not reorder them. Package i weighs weights[i]. Each day the ship departs once, carrying the next packages from the belt as long as their total weight stays within the ship's capacity; whatever doesn't fit waits for the next day.
Your function receives the integer array weights and an integer days, and must return a single integer: the smallest ship capacity that gets every package delivered within days days.
Note the capacity can never be below the heaviest single package (it has to fit on some day) and never needs to exceed the sum of all weights (one giant trip).
Example 1:
Input: weights = [1,2,3,4,5,6,7,8,9,10], days = 5
Output: 15
Explanation: With capacity 15 the days load as (1,2,3,4,5), (6,7), (8), (9), (10) — exactly 5 days. Capacity 14 forces a sixth day, so 15 is the minimum. Splitting a single package or reordering is not allowed.
Example 2:
Input: weights = [3,2,2,4,1,4], days = 3
Output: 6
Explanation: Capacity 6 gives the loads (3,2), (2,4), (1,4) — 3 days. Any smaller capacity needs a fourth day.
Constraints:
- 1 ≤ days ≤ weights.length ≤ 5 * 10⁴
- 1 ≤ weights[i] ≤ 500
Hints:
Flip the question: instead of "what is the best capacity?", ask the easier check "given a capacity c, how many days does the greedy loading take?" — fill each day until the next package would overflow, then start a new day.
That check is monotone: if capacity c works, every capacity above c works too. So the answers form a ✗✗✗✓✓✓ line between max(weights) and sum(weights) — binary search for the first ✓.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: weights = [1,2,3,4,5,6,7,8,9,10], days = 5
Expected output: 15