Smallest Van for the Week
MediumBinary Search
Problem
A courier must deliver parcels in the exact order they arrive; weights[i] is the weight of parcel i. Each day the van is loaded with the next parcels in line until adding one more would exceed the van's capacity, then it drives out.
Return the smallest integer capacity that lets the courier deliver all parcels within days days.
Example 1
- Input:
- weights = [4, 8, 2, 6, 5], days = 3
- Output:
- 11
With capacity 11 the days are [4], [8, 2], [6, 5]. With 10 it takes four days: [4], [8, 2], [6], [5].
Example 2
- Input:
- weights = [10, 10, 10], days = 1
- Output:
- 30
Example 3
- Input:
- weights = [7, 2, 5], days = 3
- Output:
- 7
The van must at least fit the heaviest parcel.
Constraints
- 1 ≤ days ≤ weights.length ≤ 5 · 10^4
- 1 ≤ weights[i] ≤ 500
Hint
Show the first hint
If a capacity C works, does every capacity larger than C also work?
Walkthrough
How to approach it
01Clarify before coding
- Can parcels be reordered? No, they go in arrival order, so each day is a contiguous block.
- Can a parcel be split across days? No: the van must fit the heaviest parcel.
- Is it fine to finish in fewer days? Yes, 'within days' means at most.
02Brute force
Try every capacity from max(weights) upwards and simulate the greedy loading until one fits in time.
Cost: O(n · (sum - max)) time: with 5 · 10^4 parcels of 500 kg that is up to 5 · 10^4 × 2.5 · 10^7 steps, hopeless.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.