The smallest van that still finishes on time
A depot must clear a fixed queue of orders within a number of days. Orders go out in the order they were placed, and the question is the smallest daily capacity that gets through them in time.
- Orders ship in the given order; the queue cannot be reordered.
- A day ships as many orders as fit within the capacity, and an order is never split across two days.
- The capacity must be at least the largest single order, or that order can never ship.
- Return the smallest capacity that clears the queue within the allowed days.
smallest_capacity(orders: list<int>, days: int) → int
Where you start
def smallest_capacity(orders: list[int], days: int) -> int:
Worked examples
| Call | Result |
|---|---|
smallest_capacity([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 5) | 15 |
smallest_capacity([3, 2, 2, 4, 1, 4], 3) | 6 |
smallest_capacity([1, 2, 3, 1, 1], 4) | 3 |
smallest_capacity([5], 1) | 5 |
Hint
Do not search the orders — search the answer. Capacity is somewhere between the largest order and the sum of them all, and "does this capacity finish in time" only ever goes from no to yes.
Reference solution in Python
def smallest_capacity(orders: list[int], days: int) -> int:
if not orders:
return 0
lo, hi = max(orders), sum(orders)
def fits(capacity):
used, room = 1, capacity
for order in orders:
if order > room:
used += 1
room = capacity
room -= order
return used <= days
while lo < hi:
mid = (lo + hi) // 2
if fits(mid):
hi = mid
else:
lo = mid + 1
return lo