Binary search on the answer

A warehouse must ship parcels in their recorded order over a fixed number of days. It can choose where one day's batch ends, but it cannot split a parcel or move later parcels ahead. The question is the smallest daily weight capacity that can finish the work.

Guessing the batch boundaries directly creates many possibilities. Checking one proposed capacity is much easier: fill a day until the next parcel would exceed it, then start another day.

Choosing a daily shipping capacity

Binary search applies to a monotone feasibility predicate, not only to a sorted input slice. If a capacity works, every larger capacity works. The maximum single weight is a lower bound and total weight an upper bound.

Asking whether a capacity is enough

With weights [2, 3, 4] and two days, capacity 4 needs three batches, while 5 permits [2, 3] | [4]. Any capacity above 5 also works. That false-then-true boundary is what binary search needs. Search between the heaviest parcel and the total weight, keeping a feasible midpoint as a possible answer rather than skipping past it.

weights, days := []int{2, 3, 4}, 2
low, high := 4, 9 // Heaviest parcel and total weight.
capacity := low + (high-low)/2
groups, load := 1, 0
for _, weight := range weights {
	if load+weight > capacity {
		groups++
		load = 0
	}
	load += weight
}
fmt.Println(capacity, groups <= days) // 6 true

Finding the first capacity that works

The feasibility scan greedily fills one contiguous group before opening another. Sorting would change the required order. Test boundary capacities and excess-day cases; the off-by-one usually lies in choosing the first feasible result. This pattern also models bounded batches and time budgets when feasibility is monotone.

One feasibility check scans n parcels with constant working state. Binary search needs O(log(R+1)) checks across the integer candidate range R, rather than trying every capacity. The range depends on the weight totals, not only the parcel count. Reordering or splitting parcels would change the feasibility problem.

A larger working capacity would meet the deadline but overstate what the warehouse actually needs.