MediumArrayBinary SearchGreedy

Capacity To Ship Packages Within D Days

1 approach, code in every language

A conveyor belt feeds a ship a sequence of packages, each with a known weight. Every day the ship is loaded with packages taken from the front of the belt in their given order, and the combined weight loaded on any single day cannot exceed the ship's capacity. The order of packages is fixed and cannot be rearranged.

Given the list of weights and a target number of days, find the smallest ship capacity that still allows every package to be shipped within that many days.

Example 1

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

Output: 15

With capacity 15 the loads can be (1..5), (6,7), (8), (9), (10) across five days. Any smaller capacity forces a sixth day.

Example 2

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

Output: 8

Capacity 8 lets each day carry two boxes: (4,4) and (4,4). Capacity 7 would require three days.

Constraints

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

Binary Search on Capacity

Binary search over possible capacities, greedily simulating shipments to count the days each capacity needs.

Loading animation…

Intuition

The capacity must be large enough to carry the heaviest single package, so that sets the lower bound, while carrying every package on one day sets the upper bound. For any fixed capacity, a greedy left-to-right pass gives the exact number of days required: keep adding packages until the next one would overflow, then start a new day. Larger capacities never need more days, so the day count decreases monotonically as capacity rises. Binary search then homes in on the smallest capacity whose day count fits within the allowed limit.

Algorithm walkthrough

1Set lo to the heaviest package and hi to the sum of all weights.
2Choose mid as a candidate capacity between lo and hi.
3Simulate loading: accumulate weights, and whenever the next package would exceed mid, roll over to a new day and reset the load to that package.
4If the simulated day count is within the allowed days, capacity mid works, so lower hi to mid; otherwise raise lo to mid + 1.
5The loop ends when lo equals hi, which is the minimum feasible capacity.

Implementation

class Solution:
    def shipWithinDays(self, weights: List[int], days: int) -> int:
        def daysNeeded(capacity: int) -> int:
            used, load = 1, 0
            for w in weights:
                if load + w > capacity:
                    used += 1
                    load = w
                else:
                    load += w
            return used

        lo, hi = max(weights), sum(weights)
        while lo < hi:
            mid = (lo + hi) // 2
            if daysNeeded(mid) <= days:
                hi = mid
            else:
                lo = mid + 1
        return lo

Time

O(n log S) where S is the sum of all weights

Space

O(1)

One O(n) simulation per binary search step, roughly log S steps.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Binary Search

After the pattern

Now solve one you haven't seen.

Kiln Load Ceiling is our own problem on the technique behind Capacity To Ship Packages Within D Days: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free