Capacity To Ship Packages Within D Days

Intuition

The capacity must be large enough to carry the heaviest single package, so that sets the lower bound, while carrying every package on one day sets the upper bound. For any fixed capacity, a greedy left-to-right pass gives the exact number of days required: keep adding packages until the next one would overflow, then start a new day. Larger capacities never need more days, so the day count decreases monotonically as capacity rises. Binary search then homes in on the smallest capacity whose day count fits within the allowed limit.

Algorithm walkthrough

1. 1Set lo to the heaviest package and hi to the sum of all weights.
2. 2Choose mid as a candidate capacity between lo and hi.
3. 3Simulate loading: accumulate weights, and whenever the next package would exceed mid, roll over to a new day and reset the load to that package.
4. 4If the simulated day count is within the allowed days, capacity mid works, so lower hi to mid; otherwise raise lo to mid + 1.
5. 5The loop ends when lo equals hi, which is the minimum feasible capacity.

Implementation

class Solution:
    def shipWithinDays(self, weights: List[int], days: int) -> int:
        def daysNeeded(capacity: int) -> int:
            used, load = 1, 0
            for w in weights:
                if load + w > capacity:
                    used += 1
                    load = w
                else:
                    load += w
            return used

        lo, hi = max(weights), sum(weights)
        while lo < hi:
            mid = (lo + hi) // 2
            if daysNeeded(mid) <= days:
                hi = mid
            else:
                lo = mid + 1
        return lo