Smallest ship capacity

mediumBinary searchGreedy choice target 25 min

Smallest ship capacity

Not solved yetLeetCode 1011. Capacity To Ship Packages Within D Days

Packages wait on a conveyor belt in a fixed order; package i weighs weights[i]. A ship sails once a day. Each day it carries the next few packages from the front of the belt, and their total weight must be at most the ship's capacity, the most weight it can carry. Packages cannot be split or reordered.

Return the smallest capacity that ships every package within days days.

Example 1

Inputweights = [4, 2, 3, 5, 1], days = 3Output6

Capacity 6 ships [4, 2], then [3], then [5, 1]. Capacity 5 needs four days: [4], [2, 3], [5], [1].

Example 2

Inputweights = [3, 3, 3, 3], days = 2Output6

Capacity 6 ships two packages a day: [3, 3] and [3, 3]. Capacity 5 fits only one 3 at a time, so it needs four days.

Example 3

Inputweights = [7, 1, 1, 1], days = 4Output7

The ship must lift the 7 at some point, and capacity 7 already finishes in two days.

Constraints

1 ≤ days ≤ len(weights) ≤ 5 · 10⁴
1 ≤ weights[i] ≤ 500

Plan it first

Write a line for each before you code, then say them out loud. Compare with the Approach tab afterwards.

Walk In what order will you visit the input?Notebook What will you write down as you go?Promise What stays true after every step?Cost Time and space, in Big O.

Run examples checks the examples. Submit runs every test, including edge cases and, when the problem has one, a speed check on a large input.

Same pattern