Binary search on the answer for shipping capacity
Find the smallest daily capacity that clears an ordered manifest. Trace the feasibility check, prove its greedy rule, and test both sides of the answer.
A dispatch planner has two sailings left and five pallets waiting at the dock. They weigh 8, 2, 4, 7 and 3 tonnes, in loading order. Dividing the total by two gives 12 tonnes per sailing. Try drawing the line between the two loads. After the second pallet the loads weigh 10 and 14. After the third they weigh 14 and 10. A 12-tonne ship leaves freight behind, even though its two trips provide precisely as much capacity as the freight weighs.
A planner could try a 13-tonne ship, then a 14-tonne ship, and keep the first one that clears the dock. That finds the right answer. It also makes the number of trials depend on the unit someone chose for the manifest. Enter the same weights in kilograms and stepping one unit at a time becomes a very different proposition.
The pallets stay in arrival order. The sorted sequence you can search is imaginary: write down every whole-number capacity, in ascending order, and mark whether it can ship the manifest within the deadline. A successful loading plan still works on any bigger ship. There can be only one boundary between failure and success. Go's standard library gives this shape of search an explicit contract: the predicate turns true at some index and stays true thereafter. Go sort.Search documentation
Two bounds come directly from the problem. Every indivisible pallet has to fit, so the answer is at least the weight of the heaviest one. The sum of all weights is sufficient whenever at least one sailing is available. On the example these bounds are 8 and 24. They include the answer even when a single pallet is the entire manifest.
-
Start with 8 through 24
- 8
- 16
- 24
Capacity 16 finishes in two loads. Keep 16 as the new upper bound.
-
Search 8 through 16
- 8
- 12
- 16
Capacity 12 needs three loads. The smallest candidate left is 13.
-
Search 13 through 16
- 13
- 14
- 16
Capacity 14 works. The only candidates still in contention are 13 and 14.
-
Search 13 through 14
- 13
- 14
Capacity 13 fails. The range closes at 14.
The yes-or-no question inside the search deserves more care than the midpoint arithmetic. For a given capacity, load consecutive pallets until the next would take the ship over the limit. That pallet starts the next sailing. An exact fit belongs on the current sailing. Starting a fresh load on equality needlessly spends a day and can make a perfectly feasible capacity look too small.
At capacity 13, the first ship takes 8 and 2. Adding 4 would make 14. The second ship takes 4 and 7. Adding 3 would also make 14, so a third sailing is necessary. Could leaving a pallet behind on the first day rescue the schedule? With a lighter first load the second day starts farther back in the same queue. That gives it at least as much work to do before it can reach the last pallet.
The same reasoning extends past two days. After the first sailing, the greedy plan has covered at least as long a prefix as any other legal plan. Suppose that is still true after some number of sailings. On the next day, the greedy ship can cover whatever part of the other plan's next load remains ahead of it: those pallets are a suffix of a load that already fits. If it has already passed that load, it is ahead anyway. Each day preserves the lead. This proves that when the greedy check runs out of days, every plan for that capacity runs out of days.
static bool Fits(int[] weights, int days, long capacity)
{
int loads = 1;
long used = 0;
foreach (int weight in weights)
{
if (weight > capacity) return false;
if (used + weight > capacity)
{
loads++;
if (loads > days) return false;
used = 0;
}
used += weight;
}
return true;
}The standalone check assumes a nonempty manifest of positive weights and at least one day. It handles a capacity below the largest pallet too, which is handy when testing the value just below the final answer. It reads the original order and stores two running totals. Sorting the manifest to help the binary search would quietly give the planner permission to move pallets around on the dock.
A failed trial rules out that capacity and every smaller one. A successful trial might be the exact capacity you came looking for.
The asymmetry determines both assignments in the loop. Start with a closed interval containing the minimum and a feasible upper endpoint. On success, move the upper endpoint to the middle. On failure, move the lower endpoint one past the middle. When two consecutive values remain, rounding the midpoint down tests the lower one, and either outcome closes the range.
static long MinimumCapacity(int[] weights, int days)
{
ArgumentOutOfRangeException.ThrowIfNegativeOrZero(days);
if (weights.Length == 0) return 0;
long low = 0;
long high = 0;
foreach (int weight in weights)
{
ArgumentOutOfRangeException.ThrowIfNegativeOrZero(weight);
low = Math.Max(low, weight);
high += weight;
}
while (low < high)
{
long middle = low + (high - low) / 2;
if (Fits(weights, days, middle))
high = middle;
else
low = middle + 1;
}
return low;
}The example API defines an empty manifest to require zero capacity. For a nonempty manifest, setting days to one forces the answer to be the total weight. Letting each pallet have its own sailing forces it down to the heaviest pallet. Both are useful tests of initialization, particularly when the interval begins with its endpoints already equal. Keeping the sum and capacity in a long also lets two pallets of int.MaxValue share one sailing without wrapping the upper bound.
Each trial takes at most one pass through the weights. If the inclusive range has W candidate capacities, the loop takes at most ceil(log2 W) trials, plus the initial pass to find the bounds. A range of 200,000 capacities costs at most 18 trials. Those are counts of manifest scans, independent of CPU speed. An early exit saves work on failed trials that exhaust their sailing allowance near the beginning. The additional storage stays constant. The distinction between counting passes and timing a particular implementation also comes up in Big O in production.
You can check a proposed answer without having a second optimization algorithm. For the five-pallet manifest, call Fits at 14 and require success, then at 13 and require failure. Together with monotonicity those observations certify the minimum. For a small random manifest, an even more independent oracle is to enumerate all cut positions. With two sailings, take the larger load weight at each cut, then the smallest of those values. That oracle shares neither the greedy packer nor the search loop.
A change to the dispatch rules can invalidate just one part of this reasoning. Suppose a forklift may reorder pallets before loading. At capacity 12 our two ships could take 8 with 4, then 2 with 7 and 3. A bigger ship still helps, so the search boundary survives. The old loading check would report failure at 12 and make the outer loop converge to a wrong answer. When reusing binary search on another planning problem, justify the yes-or-no test against its own rules first.
The Ship Packages Within D Days kata in C# coding challenges gives the planner a much larger manifest. If your cut-position oracle agrees on small inputs and the larger case still misses its budget, count how many times your program reads each weight. Katabench's performance guide explains how that difference shows up in grading.
Practice what you just read
- Open in the editor: Ship Packages Within D Days
Algorithm Medium Free, no account needed
Ship Packages Within D Days
Smallest ship capacity that delivers the conveyor belt on schedule.
- Open in the editor: Koko Eating Bananas
Algorithm Medium Free, no account needed
Koko Eating Bananas
The slowest eating speed that still finishes every pile in time.
More like this: C# coding challenges →