Description
A conveyor belt has packages that must be shipped within days days. The ith package has weight weights[i]. Each day, we load packages in order onto a ship. We may not load more than the ship's weight capacity. Return the least weight capacity of the ship that will ship all packages within days days.
Examples
Input:
weights = [1,2,3,4,5,6,7,8,9,10], days = 5Output:
15Explanation:
Ship with capacity 15: [1,2,3,4,5], [6,7], [8], [9], [10].
Input:
weights = [3,2,2,4,1,4], days = 3Output:
6Explanation:
Ship with capacity 6: [3,2], [2,4], [1,4].
Input:
weights = [10,9,8,7,6], days = 2Output:
22Explanation:
Ship with capacity 22: [10,9] (19 weight), [8,7,6] (21 weight). With capacity 21, it would not be possible to fit [10,9] together since they total 19, but it would require [8,7,6] to total 21, leaving [10] and [9] for separate days requiring 3 days total. The minimum capacity that allows shipping in exactly 2 days is 22.
Constraints
- •
1 ≤ days ≤ weights.length ≤ 5 × 10⁴ - •
1 ≤ weights[i] ≤ 500