All problems

Capacity to Ship Packages

Medium · binary search

A warehouse has to send weights[i]-kilogram packages to a port by ship. The packages must be shipped in the given order, and the ship has one fixed capacity: the most weight it can carry in one trip.

Each day the ship takes a run of consecutive packages, starting right after the ones already shipped, as long as their total weight is at most the capacity. Then it sails. Every package has to be shipped within days days (using fewer days is fine).

Return the smallest capacity that makes this possible.

Examples

Example 1

Input: weights = [4, 8, 3, 6, 2, 7], days = 3

Output: 12

With capacity 12 the trips are 4 + 8, then 3 + 6 + 2, then 7. With capacity 11 the 4 and the 8 no longer fit together and four trips are needed.

Example 2

Input: weights = [5, 5, 5, 5], days = 2

Output: 10

Example 3

Input: weights = [2, 3, 1], days = 3

Output: 3

One package a day, so the ship only has to carry the heaviest one.

Constraints