Capacity to Ship Packages Within D Days — Binary Search

The Problem

A conveyor belt has packages with weights weights[i] that must be shipped in their given order. Each day you load consecutive packages onto the ship without exceeding its capacity. You want to find the minimum ship capacity that ships everything within days days.

The “in order” constraint is critical — it means you cannot rearrange packages, only split the sequence into at most days contiguous groups, each with sum at most capacity.

Intuition

Larger capacities can only reduce (or hold equal) the number of days required, so the feasibility predicate is monotonic — perfect for binary search on the answer. The bounds are tight: capacity must be at least max(weights) (otherwise some package never fits) and at most sum(weights) (one giant day). For any candidate capacity, simulate greedily: load until the next package would overflow, then start a new day. The greedy is optimal because deferring a package can only delay later loads, never save a day.

Explanation with Example

Take weights = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], days = 5. lo = 10, hi = 55.

lo=10 hi=55 mid=32 days_needed=2 <=5 -> hi=32
lo=10 hi=32 mid=21 days_needed=3 <=5 -> hi=21
lo=10 hi=21 mid=15 days_needed=5 <=5 -> hi=15
lo=10 hi=15 mid=12 days_needed=6 >5  -> lo=13
lo=13 hi=15 mid=14 days_needed=6 >5  -> lo=15
lo=15 hi=15 return 15

At capacity 15, the partition is [1,2,3,4,5][6,7][8][9][10] — five days exactly.

Code

The greedy in days_needed is provably optimal because each day we load as much as fits — postponing a package only delays the next pack and can never reduce days.

def shipWithinDays(weights, days):
    def days_needed(cap):
        d, load = 1, 0
        for w in weights:
            if load + w > cap:
                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

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 cap) {
        int d = 1, load = 0;
        for (int w : weights) {
            if (load + w > cap) {
                d++;
                load = 0;
            }
            load += w;
        }
        return d;
    }
}

#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    int shipWithinDays(vector<int>& weights, int days) {
        int lo = 0, hi = 0;
        for (int w : weights) {
            lo = 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(const vector<int>& weights, int cap) {
        int d = 1, load = 0;
        for (int w : weights) {
            if (load + w > cap) {
                d++;
                load = 0;
            }
            load += w;
        }
        return d;
    }
};

Edge Cases

If days == len(weights), each package gets its own day, so the answer is max(weights). If days == 1, the answer is sum(weights). Both extremes are exactly the lo and hi bounds.

A single-package input returns that package’s weight. The greedy correctly handles a starting load of 0.

For very large weights, sum(weights) could overflow in C++ — use long. In Python, no issue.

Complexity Analysis

Time is O(n log S) where S = sum(weights). Each iteration of the binary search does an O(n) greedy feasibility check; there are O(log S) iterations.

Space is O(1): only integer accumulators. The greedy doesn’t allocate any data structure.

How to Explain It in an Interview

Open with the monotonicity claim: more capacity, fewer required days. Then state the tight bounds: max(weights) because no day can carry less than the heaviest package, and sum(weights) because that’s enough for one day.

Walk through the greedy feasibility check: load packages until adding the next would overflow, then start a new day. Argue why greedy is optimal: deferring a package can never reduce the total number of days needed.

Finish with O(n log S) and O(1). Connect the pattern to Koko Eating Bananas and Split Array Largest Sum — same template.

Related Problems

• Koko Eating Bananas — binary search on eating speed.
• Split Array Largest Sum — DP or binary search on max subarray.
• Divide Chocolate — binary search on sweetness.
• Minimized Maximum of Products Distributed to Any Store.