☕ DSA Java Articles

Topics › Binary Search › BS on Answers

Capacity to Ship Packages Within D Days

Medium TUF ID 161 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

A conveyor belt holds n packages that must be shipped in the given order within days days. Every day we load the ship with packages from the front of the belt, in order, as long as the total weight does not exceed the ship’s capacity. Return the minimum capacity that lets all packages ship within days days.

Constraints: 1 ≤ n ≤ 5 * 10^4, 1 ≤ days ≤ n, 1 ≤ weights[i] ≤ 500.

Example 1

weights = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], days = 5
answer = 15         // days: [1,2,3,4,5] [6,7] [8] [9] [10]; capacity 14 would need 6 days

Example 2

weights = [3, 2, 2, 4, 1, 4], days = 3
answer = 6          // [3,2] [2,4] [1,4]

The order constraint is what makes this a partition problem: we are cutting the array into days contiguous blocks and want the heaviest block to be as light as possible.

The feasibility check

For a fixed capacity cap, how many days do we need? Load greedily: keep adding packages to the current day while they fit; when the next package would exceed cap, close the day and start a new one with that package. Greedy is optimal here because packages must go in order, so the only decision is where to cut, and delaying a cut for as long as possible never increases the number of days (any schedule that cuts earlier can be transformed into the greedy one without using more days).

static int daysNeeded(int[] weights, int cap) {
    int days = 1;
    long load = 0;
    for (int w : weights) {
        if (load + w > cap) { days++; load = 0; }
        load += w;
    }
    return days;
}

The function assumes cap ≥ max(weights); otherwise the heaviest package would never fit on any day. Both approaches below guarantee that by starting the search at max. load is a long purely out of habit; with the given constraints an int suffices.

Approach 1: Brute force, try every capacity

Intuition. The capacity has a natural lower bound and upper bound. It must be at least max(weights), or the heaviest package cannot ship at all. It never needs to exceed sum(weights), because with that capacity everything ships in a single day. So the candidates are max, max + 1, ..., sum. A bigger ship never needs more days, so the first capacity from the small end that fits within days is the minimum.

Algorithm.

  1. Compute max and sum of the weights.
  2. For cap = max, max + 1, ..., sum: if daysNeeded(weights, cap) ≤ days, return cap.
  3. Return sum (never reached, since cap = sum always needs one day).
static int bruteForce(int[] weights, int days) {
    int max = 0, sum = 0;
    for (int w : weights) { max = Math.max(max, w); sum += w; }
    for (int cap = max; cap <= sum; cap++) {
        if (daysNeeded(weights, cap) <= days) return cap;
    }
    return sum;
}

Complexity. Time O(n * (sum - max)): with 5 * 10^4 packages of up to 500 the range has about 2.5 * 10^7 capacities, each checked in O(n), roughly 10^12 operations. Space O(1).

Approach 2: Optimal, binary search on the capacity

Intuition. Let fits(cap) = daysNeeded(weights, cap) ≤ days. If a capacity works, any larger capacity also works: the greedy loader with a bigger ship closes a day no earlier than with a smaller ship, so it never uses more days. Over cap = max, ..., sum the predicate is F F ... F T T ... T and we want the first T. Binary search over the capacity range: on a feasible mid record it and search smaller; otherwise search larger.

Algorithm.

  1. Compute max and sum; set lo = max, hi = sum, ans = sum.
  2. While lo ≤ hi:
    • mid = lo + (hi - lo) / 2.
    • If daysNeeded(weights, mid) ≤ days: ans = mid, hi = mid - 1.
    • Else: lo = mid + 1.
  3. Return ans.
static int optimal(int[] weights, int days) {
    int max = 0, sum = 0;
    for (int w : weights) { max = Math.max(max, w); sum += w; }
    int lo = max, hi = sum, ans = sum;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (daysNeeded(weights, mid) <= days) { ans = mid; hi = mid - 1; }
        else lo = mid + 1;
    }
    return ans;
}

Dry run on weights = [3, 2, 2, 4, 1, 4], days = 3 (max = 4, sum = 16):

lo hi mid greedy days at mid days needed ≤ 3? ans next
4 16 10 [3,2,2] [4,1,4] 2 yes 10 [4, 9]
4 9 6 [3,2] [2,4] [1,4] 3 yes 6 [4, 5]
4 5 4 [3] [2,2] [4] [1] [4] 5 no 6 [5, 5]
5 5 5 [3,2] [2] [4,1] [4] 4 no 6 [6, 5] stop

Result 6.

Complexity. Time O(n log(sum)): about 25 iterations for sum ≤ 2.5 * 10^7, each an O(n) greedy scan, around 10^6 operations. Space O(1).

Why lo = max matters

Starting the search at lo = 1 is a classic bug. daysNeeded with a capacity below the heaviest package still returns some number because the greedy loop just starts a new day and then puts the oversized package on it anyway; it does not notice that the package does not fit. A capacity like that could then be reported as feasible. Starting at max guarantees every candidate is physically possible, and cap = sum guarantees the range contains at least one feasible value. In general, when you binary search on an answer, think about both ends: the low end must exclude impossible candidates, and the high end must include at least one feasible one.

Edge cases and pitfalls