#181MediumBinary Search· Binary Search on the Answer
Smallest Truck Capacity
Input format
`weights`: an array of positive integers, the package weights in conveyor order; `days`: the number of available days.
Output format
An integer: the minimum capacity that ships all packages within `days` days.
Examples
Input: weights = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], days = 5
Output: 15
Capacity 15 works: [1,2,3,4,5], [6,7], [8], [9], [10]. With capacity 14 five days are not enough.
Input: weights = [3, 2, 2, 4, 1, 4], days = 3
Output: 6
Capacity 6 gives [3,2], [2,4], [1,4] in three days; capacity 5 would need a fourth day.
Input: weights = [7], days = 1
Output: 7
A single package needs a truck that can carry it: capacity 7.
Constraints
- 1 <= days <= weights.length <= 5 * 10^4
- 1 <= weights[i] <= 500
Study first
- #binary-search
- #binary-search-on-answer
- #greedy
- #arrays