Batch capacity
HardOnline Assessment
Find the smallest capacity that lets you ship all items in a limited number of batches.
The items in weights must be processed in the given order. You split them into at most days batches, where each batch is a non-empty consecutive segment of the list. A batch is allowed only if the sum of its weights is at most the capacity. Return the smallest integer capacity for which such a split exists. Using fewer than days batches is allowed.
Input: weights, a list of positive integers, and days, a positive integer.
Output: an integer, the minimum capacity. If weights is empty, return 0.
An efficient solution (such as binary search on the capacity) is expected; inputs are large.
Example 1
- Input:
- [[3,2,5,4],2]
- Output:
- 9
- Explanation
- Two batches: [3, 2] and [5, 4] have sums 5 and 9, so capacity 9 works. With capacity 8, the 5 and 4 cannot share a batch (5 + 4 = 9), which would force a third batch. The answer is 9.
Example 2
- Input:
- [[7,1,2],10]
- Output:
- 7
- Explanation
- There are more days than items, so every item can be its own batch. The capacity only has to hold the heaviest item, 7.
Example 3
- Input:
- [[1,2,3,4,5,6,7,8,9],3]
- Output:
- 17
- Explanation
- With capacity 17: [1..5] = 15, [6, 7] = 13, [8, 9] = 17, which is 3 batches. With capacity 16 you would need a fourth batch, so the answer is 17.
Constraints
0 <= weights.length <= 100,0001 <= weights[i] <= 1,0001 <= days <= 100,000