Capacity to Ship Packages Within D Days

Problem Description

A conveyor belt has packages that must be shipped from one port to another within days days.

The i-th package on the conveyor belt has a weight of weights[i]. Each day, we load the ship with packages on the conveyor belt (in the order given by weights). We may not load more weight than the maximum weight capacity of the ship.

Return the least weight capacity of the ship that will result in all the packages on the conveyor belt being shipped within days days.

Examples

Constraints

• 1 <= days <= weights.length <= 5 * 10⁴
• 1 <= weights[i] <= 500

Binary Search on Capacity Range

The ship’s capacity must be at least the weight of the heaviest package (otherwise we can never ship it) and at most the sum of all package weights (which would allow us to ship everything on day 1). We set left = max(weights) and right = sum(weights). We run binary search. At each step, calculate the midpoint capacity mid. Determine if it is possible to ship all packages within the allowed days at capacity mid by packing them sequentially.

• If we can ship within days, mid is a valid capacity. We record it as a candidate and try to find a smaller capacity by searching the left half: right = mid - 1.
• If it takes too many days, mid is too small, so we search the right half: left = mid + 1.

Solution 1: Binary Search on Capacity Range

Perform binary search over the possible ship capacities, validating day totals.

class Solution {
    public int shipWithinDays(int[] weights, int days) {
        int left = 0;
        int right = 0;
        for (int w : weights) {
            left = Math.max(left, w); // capacity must be at least the heaviest package
            right += w; // upper bound is the sum of all packages
        }

        int result = right;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (canShip(weights, mid, days)) {
                result = mid; // record candidate
                right = mid - 1; // try smaller capacity
            } else {
                left = mid + 1; // try larger capacity
            }
        }
        return result;
    }

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

class Solution:
    def shipWithinDays(self, weights: list[int], days: int) -> int:
        left = max(weights)
        right = sum(weights)
        result = right
        
        def can_ship(capacity: int) -> bool:
            day_count = 1
            current_weight = 0
            for w in weights:
                if current_weight + w > capacity:
                    day_count += 1
                    current_weight = 0
                current_weight += w
            return day_count <= days

        while left <= right:
            mid = left + (right - left) // 2
            if can_ship(mid):
                result = mid  # record candidate
                right = mid - 1  # try smaller capacity
            else:
                left = mid + 1  # try larger capacity
                
        return result

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

class Solution {
private:
    bool canShip(const std::vector<int>& weights, int capacity, int days) {
        int dayCount = 1;
        int currentWeight = 0;
        for (int w : weights) {
            if (currentWeight + w > capacity) {
                dayCount++;
                currentWeight = 0;
            }
            currentWeight += w;
        }
        return dayCount <= days;
    }

public:
    int shipWithinDays(std::vector<int>& weights, int days) {
        int left = *std::max_element(weights.begin(), weights.end());
        int right = std::accumulate(weights.begin(), weights.end(), 0);
        int result = right;

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

Complexity Analysis

• Time Complexity: O(n log m) where n is the number of packages and m is the sum of weights. The binary search takes log m steps, and each validation pass takes O(n) time.
• Space Complexity: O(1) auxiliary space as we track boundaries using simple variables.

Where It Breaks

This solution relies on the order of packages being fixed. If packages can be rearranged or shipped in any order, this simple O(n) greedy packing check fails, and we must solve a Bin Packing variant.

Common Mistakes

• Incorrect lower bound: Initializing left to 0 or 1 instead of max(weights). If capacity is smaller than the heaviest package, the validation function will enter an infinite loop or split packages incorrectly.
• Day count starting at 0: Setting the initial dayCount to 0 instead of 1. The first package requires at least 1 day to ship.

Frequently Asked Questions

Why does binary search work here? Because the relation between ship capacity and days needed is monotonic: as capacity increases, the number of days needed to ship all packages strictly decreases.

How does this handle packages that are exactly equal to the capacity? The check currentWeight + w > capacity will trigger, starting a new day with the current package weight, which fits because the capacity is guaranteed to be at least max(weights).

← All Problems