Capacity To Ship Packages Within D Days

Binary search the capacity, greedy-pack to test it

time O(n log(sum(weights)))space O(1)

Nothing here is sorted, so there is no array to binary search. What IS sorted is the capacity line: if a 7-ton ship can finish in time then an 8-ton ship certainly can, and if a 5-ton ship cannot then neither can a 4-ton one. Feasibility flips from no to yes exactly once along that line, and binary search hunts that flip. Each guess is tested by loading the ship greedily — keep adding packages until the next one would overflow, then start a new day — which is optimal because delaying a package you could carry today can never save a day later.

Details

Animated on: weights = [3,2,2,4,1,4], days = 3 — packages must ship in the given order; find the smallest daily ship capacity that clears them all within 3 days.

Problem:Capacity To Ship Packages Within D DaysMedium

Pattern:Binary Search on Answer

Binary search the capacity, greedy-pack to test it

step 1 / 10

[0]

[1]

[2]

[3]

[4]

[5]

6 packages must go out in this exact order within 3 days. A ship smaller than 4 could never carry the heaviest package, and 16 carries everything in one day, so the answer is somewhere in [4, 16] — and raising the capacity never needs MORE days, which is the monotonicity binary search runs on.

Pseudocode

1FUNCTION shipWithinDays(weights, days):
2  low <- MAX(weights)
3  high <- SUM(weights)
4  WHILE low < high:
5    mid <- (low + high) / 2
6    IF DAYS_NEEDED(weights, mid) <= days:
7      high <- mid
8    ELSE:
9      low <- mid + 1
10  RETURN low

← / → step · space play · Home restart

Every step in words

Show all 10 steps

6 packages must go out in this exact order within 3 days. A ship smaller than 4 could never carry the heaviest package, and 16 carries everything in one day, so the answer is somewhere in [4, 16] — and raising the capacity never needs MORE days, which is the monotonicity binary search runs on.
Range is [4, 16] — 13 capacities still possible. Test the middle one, 10: whichever way it answers, half of those candidates are gone.
A 10-ton ship fills up greedily until the next package would overflow it — the first one closes after index 2, giving 2 shipments [3,2,2] | [4,1,4]. 2 <= 3, so 10 works; a smaller ship might too, so keep 10 in play and drop everything above it: high <- 10.
Range is [4, 10] — 7 capacities still possible. Test the middle one, 7: whichever way it answers, half of those candidates are gone.
A 7-ton ship fills up greedily until the next package would overflow it — the first one closes after index 2, giving 3 shipments [3,2,2] | [4,1] | [4]. 3 <= 3, so 7 works; a smaller ship might too, so keep 7 in play and drop everything above it: high <- 7.
Range is [4, 7] — 4 capacities still possible. Test the middle one, 5: whichever way it answers, half of those candidates are gone.
A 5-ton ship closes after index 1 and needs 4 shipments [3,2] | [2] | [4,1] | [4] — 4 > 3, so 5 is too small. Every capacity below 5 would need at least as many days, so discard the whole lower half: low <- 6.
Range is [6, 7] — 2 capacities still possible. Test the middle one, 6: whichever way it answers, half of those candidates are gone.
A 6-ton ship fills up greedily until the next package would overflow it — the first one closes after index 1, giving 3 shipments [3,2] | [2,4] | [1,4]. 3 <= 3, so 6 works; a smaller ship might too, so keep 6 in play and drop everything above it: high <- 6.
low and high have met at 6. Everything below it was proven to need more than 3 days and 6 itself splits into 3 shipments [3,2] | [2,4] | [1,4], so 6 is the least weight capacity that ships everything in time.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Capacity To Ship Packages Within D Days in the editor All Binary Search problems Back to roadmap