Capacity To Ship Packages Within D Days

Problem

A conveyor belt delivers packages in a fixed order, with weights given by the array weights. Every day a single ship departs carrying packages taken from the front of the belt, in order, as long as their total weight does not exceed the ship's capacity. Packages cannot be reordered or split across days. Return the smallest integer capacity that allows all packages to be shipped within days days.

• Between 1 and 100,000 packages, each weighing between 1 and 1,000 units.
• days is at least 1 and at most the number of packages, so a schedule always exists.

Examples

• weights = [8, 3, 6, 9, 2, 7, 4], days = 3 → 15. Loads [8, 3], [6, 9], [2, 7, 4] fit in 3 days; capacity 14 splits the 6 and 9 and needs a fourth day.
• weights = [4, 6, 2, 5, 3], days = 2 → 10. Loads [4, 6] and [2, 5, 3], each exactly 10.
• weights = [2, 9, 1, 1], days = 3 → 9. Loads [2], [9], [1, 1]; no capacity below 9 can carry the 9-unit package.

Hints

1. For a fixed capacity, can you simulate the shipping schedule and count how many days it takes?
2. Does a larger ship ever take more days than a smaller one? What structure does that give the set of capacities that work?
3. Binary search on the capacity between the heaviest package and the sum of all packages, using the day-count simulation as the predicate.