Capacity to Ship Packages Within D Days
Understanding the Problem
We have a sequence of packages on a conveyor belt, and we must ship them in order. We cannot rearrange packages. Each day, we load consecutive packages onto the ship until adding the next package would exceed the ship's capacity, then we stop for the day. We need to find the smallest ship capacity that lets us finish all packages within the given number of days.
The "in order" constraint shapes everything. We can't cherry-pick lighter packages to balance the load. Packages come off the belt sequentially, so the problem reduces to splitting the array into at most days contiguous segments, where each segment's sum is at most the ship's capacity. We want the smallest capacity for which such a split exists.
The answer also has firm bounds. The capacity must be at least the weight of the heaviest single package, otherwise that package could never be shipped. A capacity equal to the sum of all weights ships everything in one day. Every candidate answer lies between these two values.
Key Constraints:
1 <= weights.length <= 5 * 10^4→ With n up to 50,000, we can afford O(n log S) where S is the sum of weights. An O(n * S) brute force would be too slow since S can be up to 25,000,000.1 <= weights[i] <= 500→ Individual weights are small, but the total sum can reach 5 10^4 500 = 25,000,000. This means the search space for capacity is at most 25 million values.1 <= days <= weights.length→ An answer always exists for anydays >= 1, since a capacity ofsum(weights)ships everything on day one.
Approach 1: Linear Search on Capacity (Brute Force)
Intuition
Try every possible ship capacity in increasing order and return the first one that works. The smallest candidate is max(weights) because the ship must be able to carry at least the heaviest package. From there, we increment the capacity by 1 and simulate the shipping process until some capacity finishes within days days. Because we test capacities from smallest to largest, the first feasible one is the answer.
To test a candidate capacity, we iterate through the weights, keeping a running sum for the current day's load. When adding the next package would exceed the capacity, we start a new day. The capacity works if the total number of days needed is at most days.
Algorithm
- Compute
maxWeight(the heaviest package) andtotalWeight(sum of all packages). - For each capacity
capfrommaxWeighttototalWeight: - Simulate shipping: iterate through weights, accumulate each day's load, start a new day when the next package won't fit.
- Count the number of days needed.
- If
daysNeeded <= days, returncap. - If no smaller value worked,
totalWeightis always valid (ship everything in 1 day).
Visualization and Code
Loading animation...
- Time Complexity: O(n * S), where n is the number of packages and S = totalWeight - maxWeight is the range of capacities we search through. For each of the S candidate capacities, we do an O(n) simulation.
- Space Complexity: O(1). The simulation uses a few integer variables and no additional data structures.
The expensive part is the linear scan over capacities: up to 25 million candidate values, each tested with an O(n) simulation. The results of those tests have a structure that lets us skip almost all of them.
Approach 2: Binary Search on Answer (Optimal)
Intuition
The feasibility function is monotonic. If a ship with capacity 15 can deliver all packages within 5 days, then a ship with capacity 16 or 100 can too: the same schedule works, with room to spare. Conversely, if capacity 10 isn't enough, then 9 and 8 won't work either.
Mapped over the range of capacities, feasibility looks like [false, false, ..., false, true, true, ..., true]. We want the leftmost true, which is the binary search on answer pattern: instead of computing the answer directly, binary search the range of possible answers and test each candidate.
The bounds from the problem analysis become the search range: left = max(weights) and right = sum(weights).
For each candidate capacity mid, we run the same greedy simulation as before: iterate through the packages, accumulate weight for the current day, and start a new day whenever adding the next package would exceed mid. If the total days needed is within the limit, mid is feasible and we search the lower half for something smaller. If not, we need a bigger ship and search the upper half.
For a fixed capacity, the greedy simulation computes the minimum possible number of days, so it never wrongly rejects a feasible capacity. The argument is by induction: after each day, the greedy schedule has shipped at least as many packages as any other valid schedule, because it starts the day at least as far along the belt and then loads until the next package would not fit. Holding a package back for the next day can only leave the schedule at the same position or behind, so it never reduces the day count.
Algorithm
- Compute
left = max(weights)andright = sum(weights). - While
left < right: - Compute
mid = left + (right - left) / 2. - Run the feasibility check with capacity
mid: - Iterate through weights, accumulating each day's load.
- When adding the next package exceeds
mid, start a new day. - Count total days needed.
- If
daysNeeded <= days, the capacity is sufficient. Setright = mid(try smaller). - Otherwise, set
left = mid + 1(need more capacity). - Return
left.
Visualization and Code
Loading animation...
- Time Complexity: O(n * log(S)), where n is the number of packages and S = sum(weights) - max(weights) is the size of the search range. Binary search runs O(log S) iterations, each running the greedy simulation in O(n).
- Space Complexity: O(1). Both the binary search and the greedy simulation use a constant number of integer variables.