The challenge
Find the minimum capacity that ships all packages in their given order within D days.
Nonempty positive integer weights and D ≥ 1. Invalid D returns −1. Total weight fits a signed 64-bit integer.
Example
[1, 2, 3, 1, 1], D = 4 → capacity 3.
Use the walkthrough below to inspect the input and each state change.
See Minimum shipping capacity, step by step
Inspect the comparison, the invariant, and the next boundary.
Answer-space searchD = 4
Tested candidate / qualifying inputResolved positionParameters shown above
- Left
- 3
- Middle
- —
- Right
- 8
Step 01 / 5
Search the answer range
The candidate is a number, rather than an input index. Keep the smallest feasible value.
left = 3; right = 8Recorded result so far
Not resolved
View exact input
Input: [1,2,3,1,1] · D = 4
Put it into code
Greedily fill each day until the next package would exceed capacity. Larger capacities cannot need more days.
Indices are zero-based. C++ uses C++17 or later.
def ship_capacity(nums, days):
# Nonempty positive weights, kept in input order.
if days < 1:
return -1
left, right = max(nums), sum(nums)
while left < right:
mid = left + (right - left) // 2
parts, load = 1, 0
for value in nums:
if load + value > mid:
parts += 1
load = 0
load += value
if parts <= days:
right = mid
else:
left = mid + 1
return left#include <algorithm>
#include <numeric>
#include <vector>
long long ship_capacity(const std::vector<int>& nums, int days) {
if (days < 1) return -1;
long long left = *std::max_element(nums.begin(), nums.end());
long long right = std::accumulate(nums.begin(), nums.end(), 0LL);
while (left < right) {
long long mid = left + (right - left) / 2, load = 0;
int parts = 1;
for (int value : nums) {
if (load + value > mid) { ++parts; load = 0; }
load += value;
}
if (parts <= days) right = mid;
else left = mid + 1;
}
return left;
}