Capacity To Ship Packages Within D Days

Problem Statement

Packages with given weights must ship in order within days days. A ship has a fixed daily capacity. Find the minimum capacity that lets all packages ship within days days.

Example

Input:  weights = [1,2,3,4,5,6,7,8,9,10], days = 5
Output: 15

Approach

Binary search the capacity in [max(weights), sum(weights)]. For a candidate capacity, greedily load packages day by day and count the days needed; fewer days means the capacity is feasible, so try smaller. The predicate "ships within D days" is monotone in capacity.

Complexity

• Time: O(n log(sum - max))
• Space: O(1)

Solution Code

Python

def shipWithinDays(weights, days):
    left, right = max(weights), sum(weights)
    while left < right:
        mid = (left + right) // 2
        need, cur = 1, 0
        for w in weights:
            if cur + w > mid:
                need += 1
                cur = 0
            cur += w
        if need <= days:
            right = mid
        else:
            left = mid + 1
    return left

Java

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 - left) / 2;
        int need = 1, cur = 0;
        for (int w : weights) {
            if (cur + w > mid) { need++; cur = 0; }
            cur += w;
        }
        if (need <= days) right = mid;
        else left = mid + 1;
    }
    return left;
}

C++

int shipWithinDays(vector<int>& weights, int days) {
    int left = 0, right = 0;
    for (int w : weights) { left = max(left, w); right += w; }
    while (left < right) {
        int mid = left + (right - left) / 2;
        int need = 1, cur = 0;
        for (int w : weights) {
            if (cur + w > mid) { need++; cur = 0; }
            cur += w;
        }
        if (need <= days) right = mid;
        else left = mid + 1;
    }
    return left;
}

Key Takeaways

• Lower bound is max(weights) (one package must fit), upper bound is sum (one day).
• The greedy day-count is the feasibility test inside the binary search.
• Reference: LeetCode 1011 (Capacity To Ship Packages Within D Days).