Capacity to Ship Packages within D Days

You are given an array of package weights and a number D representing the number of days within which all the packages must be delivered. Each day, you can ship packages in the given order, but the total weight of the packages shipped on a day cannot exceed a certain ship capacity.

Your task is to determine the minimum weight capacity of the ship so that all packages can be shipped within D days.

Note: Packages must be shipped in order and cannot be split.

Understanding the Problem

We are given an array of package weights and a number D representing the number of days within which all packages must be shipped. The task is to find the minimum ship capacity that allows us to ship all the packages in order, within D days. Each day, the ship can carry a contiguous group of packages without exceeding its maximum weight capacity. Packages cannot be split and must be shipped in the given order.

Step-by-Step Solution with Example

Step 1: Understand the Role of Capacity

Capacity means the maximum total weight the ship can carry in a single day. For instance, if the capacity is 10, then the ship can carry packages like [3,7], but not [6,5] since 6+5 = 11 exceeds the limit.

Step 2: Binary Search Strategy

We aim to find the smallest valid capacity. To do this efficiently, we use binary search between two limits:

• Lower bound: the maximum weight of any single package (since the ship must at least carry that).
• Upper bound: the total weight of all packages (meaning all shipped in one day).

Step 3: Check If a Given Capacity Works

For any candidate capacity in our binary search, we simulate the shipping process:

• Start on day 1 with current day load = 0.
• Iterate through the packages:
• Add the current package to the current day's load.
• If this exceeds the capacity, increment the day count and start a new day with the current package.

If the number of days used exceeds D, the capacity is too small. Otherwise, it's a valid capacity and we try smaller values to minimize it.

Step 4: Example

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

Step-by-step:
- The max weight is 10 → minimum possible capacity.
- Total weight is 55 → maximum possible capacity.
- We perform binary search between 10 and 55.

First mid = 32:
- Simulated days needed: 3 (valid, try smaller capacity)
Next mid = 21:
- Simulated days needed: 4 (valid, try smaller)
Next mid = 15:
- Simulated days needed: 5 (valid, try smaller)
Next mid = 12:
- Simulated days needed: 6 (too many, try larger)
Next mid = 13:
- Simulated days needed: 5 (valid, try smaller)
...
Eventually, we find that the minimum capacity that allows shipping in 5 days is 15.

Edge Cases

• Only one package: If there's one package and one day, the capacity must be equal to the package weight.
• More days than packages: We can ship one package per day, so capacity only needs to handle the largest package.
• Empty package list: No packages to ship. Return 0 or handle as a special case depending on constraints.
• Very large weights or days: Use 64-bit integers to avoid overflow when summing weights or calculating mid values in binary search.

Finally

This problem is a classic example of using binary search on the answer space. Instead of iterating through all possible capacities, we strategically test midpoints to narrow the range. By simulating the shipping process for each tested capacity, we ensure the chosen value truly satisfies the D-day constraint. The logic can be extended to similar scheduling and load-balancing problems as well.

1. Set the search range: low = max(weights) and high = sum(weights).
2. While low ≤ high:
3. → Compute mid = (low + high) / 2.
4. → Check if it’s possible to ship all packages within D days using mid as the capacity.
5. → If possible, store mid as answer and try to minimize (high = mid - 1).
6. → Otherwise, increase capacity (low = mid + 1).
7. Return the minimum valid capacity found.

#include <stdio.h>

int canShip(int weights[], int n, int D, int capacity) {
    int days = 1, total = 0;
    for (int i = 0; i < n; i++) {
        if (total + weights[i] > capacity) {
            days++;
            total = 0;
        }
        total += weights[i];
    }
    return days <= D;
}

int shipWithinDays(int weights[], int n, int D) {
    int low = weights[0], high = 0;
    for (int i = 0; i < n; i++) {
        if (weights[i] > low) low = weights[i];
        high += weights[i];
    }
    int result = high;
    while (low <= high) {
        int mid = (low + high) / 2;
        if (canShip(weights, n, D, mid)) {
            result = mid;
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    return result;
}

int main() {
    int weights[] = {1,2,3,4,5,6,7,8,9,10};
    int n = sizeof(weights) / sizeof(weights[0]);
    int D = 5;
    printf("Minimum capacity: %d\n", shipWithinDays(weights, n, D));
    return 0;
}

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

bool canShip(const vector<int>& weights, int D, int capacity) {
    int days = 1, total = 0;
    for (int w : weights) {
        if (total + w > capacity) {
            days++;
            total = 0;
        }
        total += w;
    }
    return days <= D;
}

int shipWithinDays(vector<int>& weights, int D) {
    int low = *max_element(weights.begin(), weights.end());
    int high = accumulate(weights.begin(), weights.end(), 0);
    int result = high;
    while (low <= high) {
        int mid = (low + high) / 2;
        if (canShip(weights, D, mid)) {
            result = mid;
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    return result;
}

int main() {
    vector<int> weights = {1,2,3,4,5,6,7,8,9,10};
    int D = 5;
    cout << "Minimum capacity: " << shipWithinDays(weights, D) << endl;
    return 0;
}

def shipWithinDays(weights, D):
    def canShip(capacity):
        days = 1
        total = 0
        for weight in weights:
            if total + weight > capacity:
                days += 1
                total = 0
            total += weight
        return days <= D

    low = max(weights)
    high = sum(weights)
    result = high

    while low <= high:
        mid = (low + high) // 2
        if canShip(mid):
            result = mid
            high = mid - 1
        else:
            low = mid + 1

    return result

weights = [1,2,3,4,5,6,7,8,9,10]
D = 5
print("Minimum capacity:", shipWithinDays(weights, D))

public class ShipWithinDays {
    public static boolean canShip(int[] weights, int D, int capacity) {
        int days = 1, total = 0;
        for (int w : weights) {
            if (total + w > capacity) {
                days++;
                total = 0;
            }
            total += w;
        }
        return days <= D;
    }

    public static int shipWithinDays(int[] weights, int D) {
        int low = Integer.MIN_VALUE, high = 0;
        for (int w : weights) {
            low = Math.max(low, w);
            high += w;
        }
        int result = high;
        while (low <= high) {
            int mid = (low + high) / 2;
            if (canShip(weights, D, mid)) {
                result = mid;
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return result;
    }

    public static void main(String[] args) {
        int[] weights = {1,2,3,4,5,6,7,8,9,10};
        int D = 5;
        System.out.println("Minimum capacity: " + shipWithinDays(weights, D));
    }
}

function shipWithinDays(weights, D) {
    const canShip = (capacity) => {
        let days = 1, total = 0;
        for (let weight of weights) {
            if (total + weight > capacity) {
                days++;
                total = 0;
            }
            total += weight;
        }
        return days <= D;
    };

    let low = Math.max(...weights);
    let high = weights.reduce((a, b) => a + b, 0);
    let result = high;

    while (low <= high) {
        let mid = Math.floor((low + high) / 2);
        if (canShip(mid)) {
            result = mid;
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }

    return result;
}

let weights = [1,2,3,4,5,6,7,8,9,10];
let D = 5;
console.log("Minimum capacity:", shipWithinDays(weights, D));

package main

import (
    "fmt"
)

func canShip(weights []int, D, capacity int) bool {
    days, total := 1, 0
    for _, w := range weights {
        if total + w > capacity {
            days++
            total = 0
        }
        total += w
    }
    return days <= D
}

func shipWithinDays(weights []int, D int) int {
    low, high := weights[0], 0
    for _, w := range weights {
        if w > low {
            low = w
        }
        high += w
    }
    result := high
    for low <= high {
        mid := (low + high) / 2
        if canShip(weights, D, mid) {
            result = mid
            high = mid - 1
        } else {
            low = mid + 1
        }
    }
    return result
}

func main() {
    weights := []int{1,2,3,4,5,6,7,8,9,10}
    D := 5
    fmt.Println("Minimum capacity:", shipWithinDays(weights, D))
}

fn can_ship(weights: &Vec<i32>, d: i32, capacity: i32) -> bool {
    let mut days = 1;
    let mut total = 0;
    for &w in weights {
        if total + w > capacity {
            days += 1;
            total = 0;
        }
        total += w;
    }
    days <= d
}

fn ship_within_days(weights: Vec<i32>, d: i32) -> i32 {
    let mut low = *weights.iter().max().unwrap();
    let mut high: i32 = weights.iter().sum();
    let mut result = high;

    while low <= high {
        let mid = (low + high) / 2;
        if can_ship(&weights, d, mid) {
            result = mid;
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    result
}

fn main() {
    let weights = vec![1,2,3,4,5,6,7,8,9,10];
    let d = 5;
    println!("Minimum capacity: {}", ship_within_days(weights, d));
}

fun canShip(weights: IntArray, D: Int, capacity: Int): Boolean {
    var days = 1
    var total = 0
    for (w in weights) {
        if (total + w > capacity) {
            days++
            total = 0
        }
        total += w
    }
    return days <= D
}

fun shipWithinDays(weights: IntArray, D: Int): Int {
    var low = weights.maxOrNull() ?: 0
    var high = weights.sum()
    var result = high
    while (low <= high) {
        val mid = (low + high) / 2
        if (canShip(weights, D, mid)) {
            result = mid
            high = mid - 1
        } else {
            low = mid + 1
        }
    }
    return result
}

fun main() {
    val weights = intArrayOf(1,2,3,4,5,6,7,8,9,10)
    val D = 5
    println("Minimum capacity: ${shipWithinDays(weights, D)}")
}

func canShip(_ weights: [Int], _ D: Int, _ capacity: Int) -> Bool {
    var days = 1, total = 0
    for weight in weights {
        if total + weight > capacity {
            days += 1
            total = 0
        }
        total += weight
    }
    return days <= D
}

func shipWithinDays(_ weights: [Int], _ D: Int) -> Int {
    var low = weights.max()!
    var high = weights.reduce(0, +)
    var result = high

    while low <= high {
        let mid = (low + high) / 2
        if canShip(weights, D, mid) {
            result = mid
            high = mid - 1
        } else {
            low = mid + 1
        }
    }
    return result
}

let weights = [1,2,3,4,5,6,7,8,9,10]
let D = 5
print("Minimum capacity: \(shipWithinDays(weights, D))")

function shipWithinDays(weights: number[], D: number): number {
    const canShip = (capacity: number): boolean => {
        let days = 1, total = 0;
        for (let weight of weights) {
            if (total + weight > capacity) {
                days++;
                total = 0;
            }
            total += weight;
        }
        return days <= D;
    };

    let low = Math.max(...weights);
    let high = weights.reduce((a, b) => a + b, 0);
    let result = high;

    while (low <= high) {
        const mid = Math.floor((low + high) / 2);
        if (canShip(mid)) {
            result = mid;
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    return result;
}

const weights = [1,2,3,4,5,6,7,8,9,10];
const D = 5;
console.log("Minimum capacity:", shipWithinDays(weights, D));

Time complexity

Space complexity

O(1)

No extra space is used except a few variables for computation.