Capacity to Ship Packages Within D Days

Packages arrive in a fixed order and must be loaded onto a ship in that order, without reordering or skipping any package. Each day the ship carries the next…

Packages arrive in a fixed order and must be loaded onto a ship in that order, without reordering or skipping any package. Each day the ship carries the next packages in line, as long as their total weight does not exceed the ship's fixed capacity. Given the positive package weights and an integer `days`, return the minimum capacity that ships every package within at most `days` days. Packages cannot be split.

- `1 <= weights.length <= 100` - `1 <= days <= weights.length` - `1 <= weights[i] <= 10^4`

Example 1: input weights = [1,2,3,1,1], days = 4; output 3. With capacity 3: day 1 loads 1 + 2 = 3 (adding the next package, 3, would make 6, which is too heavy); day 2 loads [3]; day 3 loads 1 + 1 = 2. That is [1,2], [3], [1,1] in three days, within the limit of 4. Capacity 2 cannot work because it cannot carry the weight-3 package at all.

Example 2: input weights = [3,2,2,4,1,4], days = 3; output 6. With capacity 6: day 1 loads 3 + 2 = 5 (the next package, 2, would make 7); day 2 loads 2 + 4 = 6; day 3 loads 1 + 4 = 5. That is [3,2], [2,4], [1,4] in three days. Every smaller capacity needs at least four days.

Category: Binary Search. Topic: binary-search. Difficulty: Medium. Patterns: binary-search-on-answer, greedy.