The problem
A parcel office must send a row of parcels, with weights parcels, in the order they were booked. One van leaves each day. It carries the next few parcels in the row, as long as their total weight is not more than its capacity. Parcels cannot be split, and their order cannot change.
Return the smallest whole-number capacity that sends every parcel within days days.
min_capacity([3, 2, 2, 4, 1, 4], 3) # 6: [3, 2], [2, 4], [1, 4]
min_capacity([5, 1, 4], 1) # 10
min_capacity([1, 9, 1, 9, 1], 2) # 11: [1, 9, 1], [9, 1]
Limits
- 1 to 50,000 parcels, each weighing from 1 to 500,000.
daysis at least 1. The large tests must finish within a few seconds.
Builds on BSRC-4 Searching on the answer.
Continue on a laptop
Practice runs Python in the browser and needs a keyboard and a wider screen. Read the problem and open hints here, then write your solution on a laptop. Progress is saved per browser for now, so hints opened here stay on this device.
Need a hint?0 of 3 opened
- Hint 1Nudge
- Hint 2Approach Open hint 1 first
- Hint 3Pseudocode Open hint 2 first
- Worked solutionlast resort Opens after all 3 hints
Ctrl + Enter runs the tests. Tab indents; press Esc, then Tab, to leave the editor.
8 tests, not run yet
| # | Test | Result | Reads · time |
|---|---|---|---|
| 1 | The example | Not run | |
| 2 | One day | Not run | |
| 3 | A day for every parcel | Not run | |
| 4 | More days than parcels | Not run | |
| 5 | Ten parcels, five days | Not run | |
| 6 | Order matters | Not run | |
| 7 | 50,000 parcels, 100 days | Not run | |
| 8 | One very heavy parcel | Not run |