Capacity To Ship Packages Within D Days

Medium· binary search on answer· greedy check

Problem

Packages must be shipped in the given order, and each day the ship is loaded with a consecutive run of packages whose total weight does not exceed its capacity. Find the lowest ship capacity that gets every package delivered within the given number of days.

Examples

Input: weights = [1,2,3,4,5,6,7,8,9,10], days = 5

Output: 15

Loads [1..5], [6,7], [8], [9], [10] all fit in 15, and nothing smaller works.

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

Output: 6

Split as [3,2], [2,4], [1,4].

Constraints

• 1 <= days <= weights.length <= 5 * 10^4
• 1 <= weights[i] <= 500

Hints & approach

Hint 1

The capacity can never be smaller than the heaviest package, nor needs to exceed the total weight.

Hint 2

Given a capacity, you can greedily count how many days shipping takes.

Hint 3

More capacity never needs more days, so binary search between the two bounds.

Approachtry the hints first

Binary search the capacity between max(weights) and sum(weights). To test a capacity, walk the packages greedily: keep adding to today's load, and start a new day when the next package would overflow. If the day count is within the limit, the capacity is feasible and you try smaller (hi = mid); otherwise go larger (lo = mid + 1). Feasibility is monotonic, so the search finds the smallest working capacity.

Time O(n log S), S = sum of weights · Space O(1)

← PreviousKoko Eating Bananas Next →Split Array Largest Sum