Capacity to Ship Packages in D Days

Problem

A conveyor belt has packages that must be shipped within days days. The i-th package has weight weights[i]. Each day you load the ship with packages in the order given by weights (you may not reorder them). The total weight loaded on any single day cannot exceed the ship's capacity. Return the least weight capacity that lets you ship every package within days days.

Constraints

• 1 ≤ days ≤ weights.length ≤ 5·10⁴
• 1 ≤ weights[i] ≤ 500
• Lower bound on capacity: max(weights) — must fit the heaviest single package.
• Upper bound on capacity: sum(weights) — one giant day fits everything.

Approach — Binary Search

This is a Binary Search problem. The idea: repeatedly halve the search space, discarding the half that can't contain the answer. Work through the reference code below line by line, then re-derive it yourself in the editor — that's how the pattern sticks.

Complexity: O(log n) time.

Solution code

Python

class Solution:
    def shipWithinDays(self, weights, days):
        def need(cap):
            d, cur = 1, 0
            for w in weights:
                if cur + w > cap:
                    d += 1
                    cur = 0
                cur += w
            return d
        lo, hi = max(weights), sum(weights)
        while lo < hi:
            mid = (lo + hi) // 2
            if need(mid) <= days:
                hi = mid
            else:
                lo = mid + 1
        return lo

Java

class Solution {
    public int shipWithinDays(int[] weights, int days) {
        int left = 0, right = 0;
        for (int w : weights) {
            left = Math.max(left, w);
            right += w;
        }

        while (left < right) {
            int mid = (left + right) / 2;
            if (canShip(weights, days, mid)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }

    private boolean canShip(int[] weights, int days, int capacity) {
        int currentLoad = 0, daysNeeded = 1;
        for (int w : weights) {
            if (currentLoad + w > capacity) {
                daysNeeded++;
                currentLoad = 0;
            }
            currentLoad += w;
        }
        return daysNeeded <= days;
    }
}

Practice it

Reading a solution isn't the same as being able to write it under pressure. Open this problem in the in-browser editor, hide the solution, and solve it from scratch — your code runs against real test cases instantly.