Capacity to Ship Packages: Binary Search on the Answer

Packages must be shipped in the order given. weights[i] is the weight of the i-th package. Each day the ship is loaded with a run of packages from the front, without exceeding its capacity. Return the smallest capacity that clears every package within days days.

Examples

Input	Output	Why
`weights = [1,2,3,4,5,6,7,8,9,10], days = 5`	`15`	Days of 1–5, 6–7, 8, 9, 10.
`weights = [3,2,2,4,1,4], days = 3`	`6`	3+2, 2+4, 1+4.
`weights = [1,2,3,1,1], days = 4`	`3`	A capacity of 2 needs five days.

Constraints

1 ≤ days ≤ n ≤ 5 × 10⁴
1 ≤ weights[i] ≤ 500
Packages keep their order

Hints

Hint 1

Ask the easier question first: given a capacity C, can you finish in the allowed number of days? That is one greedy pass.

Hint 2

If capacity C works, does C + 1 also work? That monotonicity is what makes binary search legal.

Hint 3

The answer is between max(weights) — a single package must fit — and sum(weights), which is one day.

Where people lose marks

Starting the search at 1 rather than max(weights): the feasibility check must still be written so it never loops forever on a package that cannot fit.
Returning the midpoint when the loop ends rather than the recorded low bound.
Using (lo + hi) / 2 with large bounds in C++ or Java. Prefer lo + (hi − lo) / 2.

Dry run on `[3,2,2,4,1,4],3`

Read it one frame at a time, the way you would trace the code on paper in an interview. Each frame shows the state after the step it describes.

Step 1 / 6

Step 1 / 6

weights
302122431445
lo4hi16days3
The answer lies between max(weights) = 4 (one package must fit) and sum(weights) = 16 (everything in one day).
Step 2 / 6

capacities
4mid 1016
lo4hi16mid10daysNeeded2
Try capacity 10: the greedy split needs 2 days, which fits. So every capacity above 10 also works — discard the upper half.
Step 3 / 6

capacities
4mid 710
lo4hi10mid7daysNeeded3
Try capacity 7: the greedy split needs 3 days, which fits. So every capacity above 7 also works — discard the upper half.
Step 4 / 6

capacities
4mid 57
lo4hi7mid5daysNeeded4
Try capacity 5: the greedy split needs 4 days, which is too many. So no capacity at or below 5 works — discard the lower half.
Step 5 / 6

capacities
6mid 67
lo6hi7mid6daysNeeded3
Try capacity 6: the greedy split needs 3 days, which fits. So every capacity above 6 also works — discard the upper half.
Step 6 / 6

capacities
6mid 66
answer6
lo and hi meet at 6: the smallest capacity that clears the backlog in 3 days.

How to think about it

Two things turn this from a hard scheduling question into a short one.

Checking is easy. For a fixed capacity, greedily fill each day until the next package would overflow, then start a new day. That greedy split is optimal because delaying a package never lets you fit more later.
The check is monotone. If a capacity works, every larger capacity works. So the feasible capacities form a suffix of the number line, and binary search finds its first element.

Search the range [max(weights), sum(weights)]: below the maximum a single package would never fit, and the total always works. Each check is O(n) and the range halves each time, so the cost is O(n log(sum)). Recognising "the answer is a number, and verifying a candidate is cheaper than constructing it" is the transferable part — the same move solves minimum eating speed, splitting an array into k parts, and most "minimise the maximum" questions.

Complexity. Time O(n log Σw) · Space O(1)

The solution, in six languages

Each one is compiled and run against the test table before it is published. Java is reviewed by hand.

def ship_capacity(weights, days):
    def feasible(cap):
        used, load = 1, 0
        for w in weights:
            if load + w > cap:      # start a new day
                used += 1
                load = 0
            load += w
        return used <= days

    lo, hi = max(weights), sum(weights)
    while lo < hi:                  # find the first capacity that works
        mid = (lo + hi) // 2
        if feasible(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

#include <vector>
#include <numeric>
#include <algorithm>

static bool feasible(const std::vector<int>& w, long long cap, int days) {
    int used = 1;
    long long load = 0;
    for (int x : w) {
        if (load + x > cap) { ++used; load = 0; }
        load += x;
    }
    return used <= days;
}

long long solve(const std::vector<int>& weights, int days) {
    long long lo = *std::max_element(weights.begin(), weights.end());
    long long hi = std::accumulate(weights.begin(), weights.end(), 0LL);
    while (lo < hi) {
        long long mid = lo + (hi - lo) / 2;      // no overflow
        if (feasible(weights, mid, days)) hi = mid;
        else lo = mid + 1;
    }
    return lo;
}

class Solution {
    private boolean feasible(int[] w, long cap, int days) {
        int used = 1;
        long load = 0;
        for (int x : w) {
            if (load + x > cap) { used++; load = 0; }
            load += x;
        }
        return used <= days;
    }

    public long shipCapacity(int[] weights, int days) {
        long lo = 0, hi = 0;
        for (int x : weights) { lo = Math.max(lo, x); hi += x; }
        while (lo < hi) {
            long mid = lo + (hi - lo) / 2;
            if (feasible(weights, mid, days)) hi = mid;
            else lo = mid + 1;
        }
        return lo;
    }
}

function shipCapacity(weights, days) {
  const feasible = (cap) => {
    let used = 1, load = 0;
    for (const w of weights) {
      if (load + w > cap) { used++; load = 0; }   // start a new day
      load += w;
    }
    return used <= days;
  };

  let lo = Math.max(...weights);
  let hi = weights.reduce((a, b) => a + b, 0);
  while (lo < hi) {
    const mid = lo + ((hi - lo) >> 1);
    if (feasible(mid)) hi = mid; else lo = mid + 1;
  }
  return lo;
}

fn feasible(weights: &[i64], cap: i64, days: i64) -> bool {
    let (mut used, mut load) = (1i64, 0i64);
    for &w in weights {
        if load + w > cap {
            used += 1;
            load = 0;
        }
        load += w;
    }
    used <= days
}

fn solve(weights: &[i64], days: i64) -> i64 {
    let mut lo = *weights.iter().max().unwrap();
    let mut hi: i64 = weights.iter().sum();
    while lo < hi {
        let mid = lo + (hi - lo) / 2;
        if feasible(weights, mid, days) { hi = mid } else { lo = mid + 1 }
    }
    lo
}

-- Greedy day count for a fixed capacity, then binary search the smallest feasible one.
daysNeeded :: [Int] -> Int -> Int
daysNeeded ws cap = go ws 0 1
  where
    go []     _    used = used
    go (w:rest) load used
      | load + w > cap = go rest w (used + 1)
      | otherwise      = go rest (load + w) used

solve :: [Int] -> Int -> Int
solve ws days = search (maximum ws) (sum ws)
  where
    search lo hi
      | lo >= hi  = lo
      | daysNeeded ws mid <= days = search lo mid
      | otherwise                 = search (mid + 1) hi
      where mid = lo + (hi - lo) `div` 2

Variants to try

Return the actual split, not just the capacity: replay the greedy pass once with the answer.
Packages can be reordered: the problem becomes bin packing, which is NP-hard.
Minimise days for a fixed capacity: that is the greedy pass on its own, with no search.

Next problems

Medium20 min

Smallest ship that clears the backlog in D days

Examples

Constraints

Hints

Where people lose marks

Dry run on `[3,2,2,4,1,4],3`

How to think about it

The solution, in six languages

Variants to try

Next problems

The slowest rate that clears every queue in time

The first day enough adjacent flowers are open

Earliest time a fleet completes its trips

Keep going

The slowest rate that clears every queue in time

The first day enough adjacent flowers are open

Earliest time a fleet completes its trips

The pattern behind it

Smallest ship that clears the backlog in D days

Examples

Constraints

Hints

Where people lose marks

Dry run on [3,2,2,4,1,4],3

How to think about it

The solution, in six languages

Variants to try

Next problems

The slowest rate that clears every queue in time

The first day enough adjacent flowers are open

Earliest time a fleet completes its trips

Keep going

The slowest rate that clears every queue in time

The first day enough adjacent flowers are open

Earliest time a fleet completes its trips

The pattern behind it

Dry run on `[3,2,2,4,1,4],3`