351. Ship It in Time
A cargo company has to move parcels waiting on a dock in a fixed order. Each day one truck loads parcels from the front of the queue, in order, without exceeding its weight capacity, and then drives away. A parcel can never be split, and parcels cannot be loaded out of order.
Given the parcel weights weights in queue order and the number of days days before the deadline, return the smallest truck capacity that moves every parcel within days days. Try to beat the straightforward idea of testing every capacity in turn.
Example 1
- Input:
- weights = [4,8,2,7,3,6], days = 3
- Output:
- 12
- Explanation:
Capacity 12 works: days of [4, 8], [2, 7, 3] and [6]. A capacity of 11 would need 4 days.
Example 2
- Input:
- weights = [9,9,9], days = 3
- Output:
- 9
- Explanation:
Each parcel gets its own day, so the capacity is 9.
Constraints
1 ≤ days ≤ weights.length ≤ 105
1 ≤ weights[i] ≤ 104
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(n log S), where S is the total weight
- Space
- O(1)