Shipping capacity: search a feasible answer

Separate optimization from the yes/no test

A baseline tries capacities from the heaviest package through total weight, simulating each until one works. For total S, maximum weight M, and n packages, this costs O(n(S-M+1)) arithmetic operations. The repeated question is “Can capacity C finish within D days?” If one capacity works, any larger one also works by using the same grouping. Feasibility is monotone, so a binary search can find its first true value.

At a fixed capacity, load the next package if it fits; otherwise start a new day. The simulation invariant is that all prior packages are assigned in order and the current day's load never exceeds capacity. Its stronger optimality claim is that greedy ships at least as many prefix packages after each day as any feasible schedule at that capacity. On day one it takes the longest fitting prefix. If it is already at least as far after day k, filling the next day cannot leave it behind a competing schedule. Positive weights make the fitting-prefix argument valid. Thus if greedy needs too many days, no legal grouping can rescue C.

Search the inclusive answer interval [M, S]: M is necessary because a package cannot split, and S always works in one day. A feasible midpoint moves the upper bound to mid; an infeasible midpoint moves the lower bound to mid+1. The interval always contains the minimum feasible capacity and strictly shrinks. Time is O(n log(S-M+2)), including validation, and O(1) auxiliary space. The loop does not allocate the daily groups because only capacity is requested. Large integer arithmetic has additional bit-level cost beyond this operation count.

Follow-up 1: return a schedule with exactly D nonempty days

Predict the missing feasibility rule: for nonempty input this requires D <= n. After finding capacity, greedily construct groups, but start a new group whenever the remaining packages must each reserve one remaining day.

Splitting a group preserves the capacity bound because all weights are positive. Define the empty-shipment/exact-day policy separately. Output now costs O(n).

Follow-up 2: packages may be reordered

The old test can reject a capacity that works after reordering. Monotonicity of capacity remains, but the greedy feasibility oracle is no longer correct; exact packing may require exponential search or a bounded-size dynamic program. A senior candidate proves both monotonicity and oracle correctness independently. A lead candidate negotiates order, scale, and approximation policy before promising that binary search alone solves the changed optimization problem.

Run and check

From the repository root:

cd curriculum/01-code/02-data-structures-algorithms/problems/13-shipping-capacity
python -m unittest -v test_solution.py

Reference implementation (download file, source below) · Contract and oracle tests (download file, source below). Read the tests after your attempt. A green reference suite verifies the supplied implementation; it does not demonstrate independent transfer. Reimplement one follow-up with the reference closed and explain which old invariant no longer holds.

def _integers(values):
    if not isinstance(values, (list, tuple)) or any(type(x) is not int for x in values):
        raise ValueError("expected a list or tuple of integers, excluding bool")

def shipping_capacity(weights, days):
    _integers(weights)
    if type(days) is not int or days <= 0 or any(weight <= 0 for weight in weights):
        raise ValueError("days and weights must be positive integers")
    if not weights:
        return 0
    lo, hi = max(weights), sum(weights)
    while lo < hi:
        capacity = lo + (hi - lo) // 2
        used, load = 1, 0
        for weight in weights:
            if load + weight > capacity:
                used += 1
                load = 0
            load += weight
        if used <= days:
            hi = capacity
        else:
            lo = capacity + 1
    return lo

import itertools
import unittest
from solution import shipping_capacity

class ShippingTests(unittest.TestCase):
    def test_contract(self):
        self.assertEqual(shipping_capacity([3, 2, 2, 4, 1, 4], 3), 6)
        self.assertEqual(shipping_capacity([], 2), 0)
        self.assertEqual(shipping_capacity([5, 1], 20), 5)
        self.assertEqual(shipping_capacity([5, 1], 1), 6)
        for weights, days in [([0, 3], 2), ([1], 0), ([1], True), ([-1], 2), ([1.0], 2)]:
            with self.assertRaises(ValueError):
                shipping_capacity(weights, days)

    def test_enumerated_partition_oracle(self):
        for n in range(1, 6):
            for weights in itertools.product(range(1, 4), repeat=n):
                for days in range(1, n + 2):
                    candidates = []
                    for mask in range(1 << (n - 1)):
                        groups = []
                        start = 0
                        for i in range(n - 1):
                            if mask & (1 << i):
                                groups.append(sum(weights[start:i + 1]))
                                start = i + 1
                        groups.append(sum(weights[start:]))
                        if len(groups) <= days:
                            candidates.append(max(groups))
                    self.assertEqual(shipping_capacity(weights, days), min(candidates))

if __name__ == "__main__":
    unittest.main()