A delivery company must ship packages (each a positive weight) in the given order, over at most days days. Each day, one truck takes as many of the next packages as fit within its capacity. Packages can't be split, and the order can't change.
Write a function that returns the smallest truck capacity that ships everything within days. There's always at least one package, and days is at least 1.
text
1smallest_capacity([3, 2, 2, 4, 1, 4], 3) -> 6
2smallest_capacity([1, 2, 3, 1, 1], 4) -> 3
3smallest_capacity([10, 2], 5) -> 10
Capacity 6 in three days
3
2
2
4
1
4
Day 1: 3 + 2. Day 2: 2 + 4. Day 3: 1 + 4. Each day fits in 6.
With capacity 6 in the first example, the days are [3, 2], [2, 4], [1, 4]. Capacity 5 would need four days.
Write smallest_capacity(packages, days) in Python or smallestCapacity(packages, days) in JavaScript.
Runs privately in your browser. Nothing is sent to a server.Ctrl/⌘ + Enter to run · Esc then Tab to leave the editor
Write your function, then run it against 20 tests.
Breakdown
Stuck? Reveal one step at a time, and try again after each one.
Checking one capacity is easy
For a given capacity, load packages in order and start a new day whenever the next one doesn't fit. Count the days. This greedy check is O(n), and it's correct because filling each day as much as possible never hurts.
Step 2
Which capacities could be the answer?
At least the heaviest package (or it can't be shipped at all), and at most the total weight (everything in one day). The answer is in that range.
Step 3
The yes/no flips once
If a capacity works, any bigger one works too. So, going up through the range, the check says no, no, ..., no, yes, yes, ... That's exactly what binary search can find: the first "yes".
Does capacity c finish in 3 days?
first yes
4
0
5
1
6
2
7
3
8
4
9
5
4 and 5 need too many days (amber); 6 and up work (green).
Step 4
Search for the first yes
Binary search the capacity range. If mid works, the answer is mid or smaller: high = mid. If not, the answer is bigger: low = mid + 1. Stop when low == high.
Solution
Give it a real try first: you learn far more from a wrong attempt than from reading the answer.
Set low = max(packages) and high = sum(packages). While low < high, test mid with the greedy day count: if it fits within days, set high = mid, otherwise low = mid + 1. Return low.
python
1def smallest_capacity(packages, days):
2 def days_needed(capacity):
↑the greedy check: fill each day
3 used, load = 1, 0
4 for weight in packages:
5 if load + weight > capacity:
6 used += 1
7 load = 0
8 load += weight
9 return used
10
11 low, high = max(packages), sum(packages)
↑smallest and largest possible answers
12 while low < high: # find the first capacity that works
13 mid = (low + high) // 2
14 if days_needed(mid) <= days:
15 high = mid
↑it works: answer is mid or smaller
16 else:
17 low = mid + 1
↑too small: answer is bigger
18 return low
javascript
1function smallestCapacity(packages, days) {
2 const daysNeeded = (capacity) => {
↑the greedy check: fill each day
3 let used = 1
4 let load = 0
5 for (const weight of packages) {
6 if (load + weight > capacity) {
7 used++
8 load = 0
9 }
10 load += weight
11 }
12 return used
13 }
14 let low = Math.max(...packages)
↑smallest and largest possible answers
15 let high = packages.reduce((a, b) => a + b, 0)
16 while (low < high) { // find the first capacity that works
17 const mid = Math.floor((low + high) / 2)
18 if (daysNeeded(mid) <= days) high = mid
↑it works: answer is mid or smaller
19 else low = mid + 1
↑too small: answer is bigger
20 }
21 return low
22}
Complexity
TimeO(n log S)SpaceO(1)
O(n log S) time, where S is the total weight: about log S checks of O(n) each. O(1) extra space.
What we learned
"Smallest X such that..." with a yes/no check that flips once: binary search on the answer.
Pick tight bounds for the search range (here, heaviest package to total weight).
This template searches for the first "yes": high = mid when it works, low = mid + 1 when it doesn't, loop while low < high.