Smallest truck that delivers on schedule

Question

Packages must ship in the given order (you cannot reorder them). Each day you load consecutive packages onto one truck until the next would exceed the truck's capacity C, then that day ends. You have D days.

weights = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], D = 5
answer: C = 15
day 1: 1,2,3,4,5 (=15) | day 2: 6,7 | day 3: 8 | day 4: 9 | day 5: 10

Find the smallest capacity C that delivers all packages within D days.

Accepted Answer

Bigger trucks never need more days, so "can capacity C finish in D days?" is monotone: false for tiny C, true once C is large enough. Binary search for the first C that works. Two bounds pin the range: C must be at least max(weights) (a truck too small for the heaviest single package can never ship it), and C = sum(weights) trivially finishes in one day. The feasibility check greedily fills each day. Tracing weights = [1..10], D = 5: range starts lo, hi = 10, 55. Capacity 15 needs exactly 5 days (as shown above), capacity 14 splits the first block as 1,2,3,4 then 5,6 and ends up needing 6 day…

Smallest truck that delivers on schedule

Your answer

More Coding questions