DevOps NetworkDevOpsNetwork
Join Free
DSA patterns

Capacity To Ship Packages Within D Days

mediumBinary search

Problem statement

Packages must be shipped in the order given by the array weights. Each day, one ship loads packages from the front of the remaining line, one after another, as long as the total weight loaded that day does not exceed the ship's capacity. Packages cannot be reordered or split, and the next day continues where the previous day stopped.

Given weights and a number of days, return the smallest ship capacity that gets every package shipped within days days.

Examples

Example 1

Input: weights = [4, 8, 2, 5, 3], days = 3

Output: 10

Explanation: With capacity 10 the days are [4], [8, 2], [5, 3]. Capacity 9 needs four days: [4], [8], [2, 5], [3].

Example 2

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

Output: 6

Explanation: Two packages per day: [3, 3], [3, 3].

Hints

Approach

Binary-search the capacity between its lower and upper limits.

  1. Set lo = max(weights) (every package must fit) and hi = sum(weights) (everything in one day).
  2. While lo < hi:
    • mid = lo + (hi - lo) // 2;
    • if days_needed(mid) <= days, mid works, so the answer is mid or smaller: hi = mid;
    • otherwise lo = mid + 1.
  3. Return lo.

The greedy check is O(n) and runs O(log S) times. The greedy check is correct because loading a package as early as possible never makes a later day worse.

ComplexityTime O(n log S)Space O(1)
Python
class Solution:
def shipWithinDays(self, weights: list[int], days: int) -> int:
def days_needed(cap: int) -> int:
used, load = 1, 0
for w in weights:
if load + w > cap:
used += 1
load = 0
load += w
return used
lo, hi = max(weights), sum(weights)
while lo < hi:
mid = lo + (hi - lo) // 2
if days_needed(mid) <= days:
hi = mid
else:
lo = mid + 1
return lo

Follow-up questions

  • Return the actual split of packages into days, not just the capacity.
  • Packages may now be loaded in any order. How does the problem change?

Frequently asked questions

It models batching work in a fixed order under a per-batch limit: splitting an ordered list of database migrations or log uploads into runs that each stay under a size or time cap, and finding the smallest cap that fits in a given number of maintenance windows.

Both binary-search the answer with a monotonic check. Here, items are grouped consecutively into days, so the check is a greedy grouping pass. In Koko each pile is handled on its own with a ceiling division.

A capacity below the heaviest package can never ship it, but the greedy days_needed above does not detect that; it would open a new day and still overfill it. Starting at the maximum keeps every tested capacity valid.