Capacity to Ship Packages Within D Days

Approach

The key observation is that the predicate "we can ship all weights in <= days days using capacity c" is monotone non-decreasing in c: if a capacity works, every larger capacity also works. So the answer is the smallest c for which the predicate is true, and that boundary is exactly what binary search finds.

Key insight

The natural search interval is [max(weights), sum(weights)]:

• The lower bound is max(weights) because no day can ship a package heavier than the capacity itself.
• The upper bound is sum(weights) because one day with that capacity fits everything.

The feasibility check is a greedy single pass: pack each day until the next package would overflow, then start a new day. This is optimal because packages must ship in order, so deferring a package to the next day cannot help.

Algorithm

1. Compute lo = max(weights), hi = sum(weights).
2. While lo < hi:

   • mid = lo + (hi - lo) // 2.
   • If canShip(weights, days, mid): feasible, try smaller, hi = mid.
   • Else: infeasible, lo = mid + 1.
3. Return lo.

For canShip(weights, days, capacity):

used = 1, load = 0
for each w in weights:
  if load + w > capacity: used++, load = w, return false if used > days
  else: load += w
return true

Complexity

Metric  Value
------  -----------------------------
Time    O(n * log(sum(weights) - max(weights)))
Space   O(1)

Each feasibility check is O(n); we run O(log(W)) of them where W = sum - max.

Why it works

Greedy packing on a fixed capacity is optimal because the order is fixed: any other strategy that withholds a package would only lengthen the prefix sum without reducing the number of days. So the feasibility check correctly tells us the minimum days achievable at that capacity. Binary searching the boundary of a monotone predicate yields the smallest feasible value.

Pitfalls

• Wrong lo: setting lo = 1 lets the binary search waste iterations on infeasible values, and the off-by-one of the mid = (lo + hi) >> 1 can land on mid = 0 for some weights[i] = 0 test, but more importantly, the math invariant breaks if some weights[i] > capacity.
• Half-open vs closed: the writeup uses half-open [lo, hi) because we are looking for the SMALLEST feasible value. hi = mid on success, lo = mid + 1 on failure. The closed [lo, hi] template with an ans variable also works.
• Off-by-one in the feasibility check: if used > days (return false) goes BEFORE the next iteration's load update; double-check the order so a borderline feasible case isn't rejected.