Capacity To Ship Packages Within D Days

Medium#1011search the answer

Packages with given weights have to be shipped in their order within a number of days. Each day the ship takes the next packages in line, as long as their total weight fits its capacity. Find the smallest capacity that ships everything in time. Our example: weights [3, 2, 2, 4, 1, 4], 3 days — the answer is 6: [3, 2], [2, 4], [1, 4].

1011 Capacity To Ship Packages Within D DaysWalkthrough · 1×

Example: Weights [3, 2, 2, 4, 1, 4], 3 days. The top row is the capacities 4..16; below, the packages grouped by the day they ship on at capacity mid.

capacity45678910111213141516lopackages322414days—
capacity still possiblechecked nowloaded on its dayruled outthe answer

The heaviest package, 4, has to fit into one day: lo = 4

01/56
restart · back · play · step
Speed
1function shipWithinDays(weights, days):
2 lo = max(weights) // the heaviest has to fit
3 hi = sum(weights) // everything in one day
4 while lo < hi:
5 mid = floor((lo + hi) / 2)
6 need = 1; load = 0
7 for each w in weights:
8 if load + w > mid: need = need + 1; load = 0
9 load = load + w
10 if need <= days:
11 hi = mid // in time: keep mid
12 else:
13 lo = mid + 1
14 return lo
state
lo
4
hi
–
mid
–
need
–
load
–
historyclick a step to go back

← → step · space play/pause

Why it works

  1. A bigger ship never needs more days. So over capacities the checks "in time?" go no, …, no, yes, …, yes, and the answer is the first yes.
  2. The capacity is at least the heaviest package, or that package never ships, and at most the total weight, which ships everything in one day. So lo starts at max(weights), not at 1.
  3. To check one capacity, load the packages in order and start a new day only when the next one does not fit. Filling each day as much as possible never takes more days than any other split.

Complexity

Time O(n log s), where n is the number of packages and s their total weight: about log s capacities are tried, and each check walks over all packages. Memory O(1).

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.