Capacity to Ship Packages Within D Days, thesarfo

Weights loaded onto a ship in order, one load per day, capped at the ship’s capacity per day. Find the minimum capacity that ships everything within days days. weights=[1..10], days=5 → 15. (LeetCode problem)

Search space: [max(weights), sum(weights)] — capacity must be at least the heaviest single package, and at most shipping everything in one day.

public int shipWithinDays(int[] weights, int days) {
    int max = 0, sum = 0;
    for (int weight : weights) {
        sum += weight;
        max = Math.max(max, weight);
    }

    int left = max, right = sum;
    int answer = right;
    while (left <= right) {
        int mid = left + (right - left) / 2;

        int daysReq = findDays(weights, mid);

        if (daysReq <= days) {
            answer = mid;
            right = mid - 1; // try a smaller capacity
        } else {
            left = mid + 1; // need more capacity
        }
    }

    return left;
}

public int findDays(int[] weights, int capacity) {
    int days = 1, load = 0;
    for (int i = 0; i < weights.length; i++) {
        if (load + weights[i] > capacity) {
            days++;
            load = weights[i];
        } else {
            load += weights[i];
        }
    }
    return days;
}

Time: O(n × log(sum - max)).