Problems › TypeScript › patterns
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
Where you start
function smallestCapacity(orders: number[], days: number): number {
}Worked examples
| Call | Result |
|---|---|
smallestCapacity([1,2,3,4,5,6,7,8,9,10], 5) | 15 |
smallestCapacity([3,2,2,4,1,4], 3) | 6 |
smallestCapacity([1,2,3,1,1], 4) | 3 |
smallestCapacity([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 TypeScript
function smallestCapacity(orders: number[], days: number): number {
if (orders.length === 0) return 0;
let lo = 0;
let hi = 0;
for (const order of orders) {
if (order > lo) lo = order;
hi += order;
}
const fits = (capacity: number): boolean => {
let used = 1;
let room = capacity;
for (const order of orders) {
if (order > room) {
used += 1;
room = capacity;
}
room -= order;
}
return used <= days;
};
while (lo < hi) {
const mid = Math.floor((lo + hi) / 2);
if (fits(mid)) hi = mid;
else lo = mid + 1;
}
return lo;
}