Minimum Load Capacity to Deliver Parcels Within a Deadline
Solve this Problemweights[i] is the weight of the i-th parcel — in the given order, never splitting a single parcel across trips. Given a fixed days limit, find the smallest truck capacity that finishes delivering every parcel within that many trips.
Each trip loads parcels one after another until the next one would exceed the truck's capacity, then starts a fresh trip. No capacity below the heaviest single parcel could ever work (that parcel wouldn't fit at all), and a capacity equal to the total weight always finishes in a single trip — so the answer is guaranteed to fall somewhere between those two bounds.
The number of trips needed only ever decreases (or stays flat) as capacity grows, which makes this a binary search on the answerBinary Search on the AnswerInstead of searching a sorted array, the search runs directly over the space of possible answers (here, every candidate truck capacity). It works whenever "is this candidate good enough?" is monotonic — once a candidate works, every larger candidate keeps working too. — search directly over candidate capacities rather than trying to reason about trip splits directly.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
1 ≤ number of parcels ≤ 5 × 10⁴ - ◆
1 ≤ weights[i] ≤ 500 - ◆
1 ≤ days ≤ number of parcels
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Try Every Capacity From the Heaviest Parcel Upward
BruteThe truck loads parcels in order, never splitting one, and starts a new trip the moment the next parcel would overflow the current trip's capacity. No capacity can ever be smaller than the heaviest single parcel, and a capacity equal to the total weight always finishes in one trip — so the true answer lies somewhere in that range. Try every capacity in that range, in order, counting the trips it needs; the first one that fits within the day limit is the answer, since a bigger capacity can only ever need the same number of trips or fewer. Correct, but scanning every candidate capacity one at a time is wasteful once the weights get large.
O(n · (sum − max))O(1)1class Solution {
2 public int minShipCapacity(int[] weights, int days) {
3 int maxW = 0, sum = 0;
4 for (int w : weights) { maxW = Math.max(maxW, w); sum += w; }
5 for (int cap = maxW; cap <= sum; cap++) {
6 if (daysNeeded(weights, cap) <= days) return cap;
7 }
8 return sum;
9 }
10
11 private int daysNeeded(int[] weights, int cap) {
12 int daysUsed = 1, load = 0;
13 for (int w : weights) {
14 if (load + w > cap) { daysUsed++; load = 0; }
15 load += w;
16 }
17 return daysUsed;
18 }
19}Optimal — Binary Search on the Capacity
OptimalA bigger truck can never need more trips than a smaller one — the number of trips only ever goes down (or stays the same) as capacity grows. That monotonic relationship is exactly what binary search needs: search the candidate capacities between the heaviest parcel and the total weight, and whenever a candidate finishes within the day limit, remember it and try a smaller capacity; otherwise the truck is too small, so search bigger.
O(n · log(sum − max))O(1)1class Solution {
2 public int minShipCapacity(int[] weights, int days) {
3 int lo = 0, hi = 0;
4 for (int w : weights) { lo = Math.max(lo, w); hi += w; }
5 int ans = hi;
6 while (lo <= hi) {
7 int mid = lo + (hi - lo) / 2;
8 if (daysNeeded(weights, mid) <= days) {
9 ans = mid;
10 hi = mid - 1;
11 } else {
12 lo = mid + 1;
13 }
14 }
15 return ans;
16 }
17
18 private int daysNeeded(int[] weights, int cap) {
19 int daysUsed = 1, load = 0;
20 for (int w : weights) {
21 if (load + w > cap) { daysUsed++; load = 0; }
22 load += w;
23 }
24 return daysUsed;
25 }
26}