Smallest truck capacity to ship packages in d days
Coding problemMedium-HardAsked in: Amazon, D. E. Shaw
Packages must be shipped in the given order. Package i weighs weights[i]. Each day, a truck with a fixed capacity loads packages in order until the next package would exceed the capacity; then the day ends. A package is never split.
Return the smallest capacity that ships every package within days days.
Examples
Example 1
Input: weights = [1,2,3,4,5,6,7,8,9,10], days = 5
Output: 15
Days: [1..5], [6, 7], [8], [9], [10].
Example 2
Input: weights = [3,2,2,4,1,4], days = 3
Output: 6
Example 3
Input: weights = [1,2,3,1,1], days = 4
Output: 3
Constraints
- The list holds between 1 and 100,000 weights
- Each weight is between 1 and 500
- days is between 1 and the number of packages
Run checks the 3 examples. Submit also runs the hidden tests: edge cases, large inputs and a time limit.
Run your code to see the results here. Ctrl or Cmd + Enter runs; add Shift to submit.