Capacity to Ship Packages Within D Days

MEDIUM✓ CHIP-TIMEDLC #1011 — FULL STATEMENT ↗

The drill: Find the smallest ship capacity that gets every package shipped within a fixed number of days — packages load in their given order, one day at a time, without ever splitting a package.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

A line of packages, each with its own weight, needs to move onto a ship over a fixed number of days, and the packages must load in the exact order they're given — no rearranging, no splitting a package across two days.

Each day the ship carries packages up to some fixed weight capacity; once the next package in line would push the day's load over that capacity, the day ends and a fresh day begins with that package.

The job is to find the smallest capacity that still gets every package shipped within the day limit — too small a capacity and the days run out before the line does.

EX 01

weights = [2, 4, 6, 8, 10, 12, 14, 16, 18, 20] · days = 5

→ 30

ASCENDING WEIGHTS, TIGHT DAY BUDGET

EX 02

weights = [1, 3, 5, 2, 4, 6, 8, 7] · days = 3

→ 15

UNSORTED WEIGHTS, ORDER MATTERS

EX 03

weights = [7] · days = 1

→ 7

SINGLE PACKAGE, ONE DAY

package list holds up to a few thousand positive weights
day budget is always at least one and never exceeds the package count
packages load strictly in their given order, no reordering allowed
capacity must be at least as large as the heaviest single package

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

A larger capacity can only ever need the same or fewer days than a smaller one — days-needed is monotonic in capacity, which is what makes bisecting the capacity itself valid.

HINT 2 THE STRUCTURE

For a candidate capacity, simulate loading packages in order, starting a new day whenever the next package would overflow the current one — count how many days that takes.

HINT 3 ONE STEP FROM THE ANSWER

Binary-search capacity between max(weights) and sum(weights): if the simulated days exceed the limit, the capacity is too small — raise it; otherwise try to shrink it.

COACH'S BOARD — THE PATTERN, STEP BY STEP

THE CARGO CEILINGPATTERN · BINARY SEARCH THE CAPACITYweights = [1, 2, 3, 4, 5] · days = 3

DAYS NEEDED AT THIS CAPACITY

— empty —

STEP 1

5 packages: 1, 2, 3, 4, 5. Binary-search capacity between 5 (heaviest package) and 15 (total weight) for the smallest that ships in 3 days.

STEP 1 / 10 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/capacity-to-ship-packages-within-d-days.py — RACE PACE

LANG ▸

PACE ▸

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

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

TIME O(N LOG(SUM(WEIGHTS)))SPACE O(1)PYTHON · RACE PACE · 19 LN

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

        capacity = max(weights)
        while days_needed(capacity) > days:
            capacity += 1
        return capacity

TIME O(N · SUM(WEIGHTS))SPACE O(1)PYTHON · TRAINING PACE · 15 LN

class Solution {
    public int shipWithinDays(int[] weights, int days) {
        int lo = 0, hi = 0;
        for (int w : weights) {
            lo = Math.max(lo, w);
            hi += w;
        }
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (daysNeeded(weights, mid) <= days) {
                hi = mid;
            } else {
                lo = mid + 1;
            }
        }
        return lo;
    }

    private int daysNeeded(int[] weights, int capacity) {
        int d = 1, load = 0;
        for (int w : weights) {
            if (load + w > capacity) {
                d++;
                load = 0;
            }
            load += w;
        }
        return d;
    }
}

TIME O(N LOG(SUM(WEIGHTS)))SPACE O(1)JAVA · RACE PACE · 30 LN

class Solution {
    public int shipWithinDays(int[] weights, int days) {
        int capacity = 0;
        for (int w : weights) {
            capacity = Math.max(capacity, w);
        }
        while (daysNeeded(weights, capacity) > days) {
            capacity++;
        }
        return capacity;
    }

    private int daysNeeded(int[] weights, int capacity) {
        int d = 1, load = 0;
        for (int w : weights) {
            if (load + w > capacity) {
                d++;
                load = 0;
            }
            load += w;
        }
        return d;
    }
}

TIME O(N · SUM(WEIGHTS))SPACE O(1)JAVA · TRAINING PACE · 24 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED