Capacity To Ship Packages Within D Days
Problem statement
Packages must be shipped in the order given by the list 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 go above 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 = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], days = 5
Output: 15
Explanation: With capacity 15 the days are [1, 2, 3, 4, 5], [6, 7], [8], [9], [10]. A capacity of 14 would need six days: [1, 2, 3, 4], [5, 6], [7], [8], [9], [10].
Example 2
Input: weights = [3, 2, 2, 4, 1, 4], days = 3
Output: 6
Explanation: With capacity 6 the days are [3, 2], [2, 4], [1, 4]. With capacity 5 the packages need four days: [3, 2], [2], [4, 1], [4].
Hints
Approach
Optimal: Binary search on the capacity
Intuition
The brute force tests capacities one by one, but the answer has a pattern: if capacity c finishes in time, every bigger capacity does too. So the capacities form a row of "no, no, no, yes, yes, yes", and we want the first "yes". That is exactly what binary search finds. Look at the middle capacity: if it works, the answer is it or something smaller; if it does not, the answer is bigger. This is faster because each check throws away half of all remaining capacities.
Steps
- Set
lo = max(weights)(every package must fit) andhi = sum(weights)(everything in one day). - While
lo < hi, computemid = lo + (hi - lo) // 2. - If
days_needed(mid) <= days,midworks, so sethi = mid. - Otherwise
midis too small, so setlo = mid + 1. - When
lo == hi, returnlo.
Dry run
weights = [3, 2, 2, 4, 1, 4], days = 3, so lo = 4 and hi = 16
| lo | hi | mid | days needed | action |
|---|---|---|---|---|
| 4 | 16 | 10 | 2 | works → hi = 10 |
| 4 | 10 | 7 | 3 | works → hi = 7 |
| 4 | 7 | 5 | 4 | too small → lo = 6 |
| 6 | 7 | 6 | 3 | works → hi = 6 |
| 6 | 6 | - | - | return 6 |
Edge cases: one package gives lo == hi, so the loop does not run and the answer is that package. If days is at least the number of packages, the answer is the heaviest package.
Complexity
Time O(n log S) - The capacity lies between the heaviest package and the total weight S, and each step of the binary search halves that range, so there are about log S steps. Every step runs the O(n) day-counting pass once. For 50,000 packages and a total weight of one billion that is about 30 passes instead of up to a billion.
Space O(1) - We keep `lo`, `hi`, `mid` and the counters of the helper. Nothing grows with the input. The list is only read.
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
if __name__ == "__main__":
print(Solution().shipWithinDays([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 5))
print(Solution().shipWithinDays([3, 2, 2, 4, 1, 4], 3))RecapThe whole problem in a few lines, for the night before
- Spot it: find the smallest value that makes something feasible, where bigger is always at least as good
- Idea: binary search on the ship capacity between the heaviest package and the total weight; check feasibility by simulating the days greedily
- Cost: O(n log(sum)) time, O(1) space
- Trap: the low bound is the heaviest single package, not 1, and packages must ship in the given order
Interview follow-ups
Return the actual split of packages into days, not just the capacity.
Once binary search gives the smallest capacity, run the greedy loader one more time with that capacity. Keep a list for the current day, and when the next package would push the day's total over the capacity, close the list and start a new one. The result is a list of lists in the original order. This costs one extra O(n) pass and O(n) space for the output. The split is not unique, but every split built this way respects the capacity and uses at most
daysdays.Packages may now be loaded in any order. How does the problem change?
Each day becomes a bin of size
capacity, so checking whether a capacity works is now a bin packing question, which is NP-hard in general. The greedy check from the fixed-order version is no longer correct, because the order of packages now changes the outcome. You can still binary search the capacity, with lower boundmax(max(weights), ceil(sum / days)). The feasibility check then needs a heuristic such as first-fit decreasing, or backtracking for small inputs. A heuristic can overestimate the capacity, so the answer is only exact when the check is exact.
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. The same "binary search the answer" idea also sizes things like the smallest batch size or rate limit that meets a deadline.
Both binary search the answer with a check that only flips once. Here, packages are grouped in order into days, so the check is a greedy grouping pass. In Koko each pile is handled on its own with a ceiling division. If you can write one, the other is the same loop with a different check.
A capacity below the heaviest package can never ship it, but the greedy days_needed above does not notice that: it would open a new day and still overfill it. Starting at the maximum keeps every tested capacity valid.
If mid fits in days, the true answer is mid or smaller, so we keep mid inside the range with hi = mid. If it does not fit, mid itself is ruled out, so lo = mid + 1. Using hi = mid - 1 in the first case would throw away a valid answer.
