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.
smallestCapacity(orders: list<int>, days: int) → int
Go needs a compiler and Drill does not host one yet, so this page is the reference rather than an exercise: the problem, worked examples, and the solution in full. To type it out, the same problem runs in Python.
Where you start
func smallestCapacity(orders []int, days int) int {
}Worked examples
| Call | Result |
|---|---|
smallestCapacity([]int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, 5) | 15 |
smallestCapacity([]int{3, 2, 2, 4, 1, 4}, 3) | 6 |
smallestCapacity([]int{1, 2, 3, 1, 1}, 4) | 3 |
smallestCapacity([]int{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 Go
func smallestCapacity(orders []int, days int) int {
if len(orders) == 0 {
return 0
}
lo, hi := 0, 0
for _, order := range orders {
if order > lo {
lo = order
}
hi += order
}
for lo < hi {
mid := (lo + hi) / 2
used, room := 1, mid
for _, order := range orders {
if order > room {
used++
room = mid
}
room -= order
}
if used <= days {
hi = mid
} else {
lo = mid + 1
}
}
return lo
}