You are given a series of packages arranged on a conveyor belt. Each package has a specific weight, represented by the array weights, where the ith element indicates the weight of the ith package. These packages must be transported from one location to another within a specified number of days, denoted as days.
Every day, the ship can be loaded with one or more consecutive packages from the belt, but the total weight loaded on any single day must not exceed the ship’s maximum weight capacity. Packages must be shipped in the order they appear; no reordering is allowed.
Your task is to determine the minimum possible weight capacity the ship must have so that all the packages can be shipped within the given number of days.
Example 1:
Input: weights = [1,2,3,4,5,6,7,8,9,10], days = 5
Output: 15Example 2:
Input: weights = [3,2,2,4,1,4], days = 3
Output: 6Example 3:
Input: weights = [1,2,3,1,1], days = 4
Output: 3This is a classic minimize-the-maximum problem. Because packages must stay in order and each day must carry a contiguous segment, we can binary search the answer between the heaviest package and the total sum of all weights. For each candidate capacity, a greedy pass counts how many days are needed by loading packages in order until the next package would exceed the limit. If the required days is too large, increase the capacity; otherwise, try a smaller one. The monotonic relationship makes binary search an efficient solution.
