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 can find a minimum feasible answer even when the input values are not the search space. Here capacity is the answer: weights retain their given order, and capacity determines how many contiguous groups are needed. Enumerating capacities one by one repeatedly runs the same feasibility scan.

Positive weights make feasibility monotone. If a capacity works, any larger capacity also works. The largest weight is a lower bound and the total weight is an upper bound.

Asking whether a capacity is enough

For a trial capacity, append weights to the current group until the next would exceed it, then begin another group. Greedily filling each group cannot require more groups than ending that group earlier, because every later group would inherit at least as much remaining work. A feasible capacity uses at most the allowed days; extra days need not be used.

Search for the first feasible integer. A feasible midpoint can replace the upper bound; an infeasible midpoint rules out that capacity and all smaller ones. Calculate the midpoint arithmetically. JavaScript bitwise midpoint tricks coerce values to signed 32-bit integers and can corrupt valid larger Number bounds.

Validate days and every weight before deriving bounds, including when the weights array is empty. Reordering or splitting weights solves a different packing problem.

const low = 2 ** 32, high = low + 10;
const midpoint = low + Math.floor((high - low) / 2);
console.log(midpoint); // 4294967301: no signed 32-bit coercion

Finding the first capacity that works

A feasibility scan costs O(n) with constant state. Searching capacities costs O(n log(S+1)), where S is the capacity interval width. Use this technique for monotone resource/cost thresholds, not predicates that switch between feasible and infeasible more than once. The baseline capacity enumeration remains useful on small instances.

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