Capacity To Ship Packages Within D Days

NeetCode: Capacity To Ship Packages Within D Days · LeetCode: 1011. Capacity To Ship Packages Within D Days · Difficulty: Medium

Packages with the given weights must be shipped in order, one ship load per day, and a load may not exceed the ship's capacity. Return the least capacity that lets you ship all packages within days days.

Example

Text

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

Two facts bound the answer. The capacity must be at least the heaviest package (otherwise it could never ship) and at most the total weight (everything ships in one day). Also, if capacity c works then any larger capacity works, so feasibility is monotonic.

To check a capacity, simulate greedily: load packages in order and start a new day when the next one would overflow.

Brute force: try each capacity in increasing order

Start at max(weights) and test capacities one by one until the simulation finishes within days. The first that works is the answer. Each test costs O(n) and there can be up to sum - max candidates.

LeetCode's Java signature is int shipWithinDays(int[] weights, int days). The total weight is an int sum; a problem with larger sums would need long, because int addition wraps silently. An empty weights array returns 0, a case the problem does not produce.

Java

public class Main {
    static class Solution {
        private int daysNeeded(int[] weights, int capacity) {
            int days = 1;
            int load = 0;
            for (int w : weights) {
                if (load + w > capacity) {
                    days++;
                    load = 0;
                }
                load += w;
            }
            return days;
        }

        public int shipWithinDays(int[] weights, int days) {
            if (weights.length == 0) {
                return 0;
            }
            int max = 0;
            for (int w : weights) {
                max = Math.max(max, w);
            }
            int capacity = max;
            while (daysNeeded(weights, capacity) > days) {
                capacity++;
            }
            return capacity;
        }
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.shipWithinDays(new int[] {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, 5));
        System.out.println(s.shipWithinDays(new int[] {3, 2, 2, 4, 1, 4}, 3));
        System.out.println(s.shipWithinDays(new int[] {1, 2, 3, 1, 1}, 4));
        System.out.println(s.shipWithinDays(new int[] {}, 3));
    }
}

Output

Time: O(n * (sum - max)). Space: O(1).

Optimal: binary search on the capacity

Since feasibility is monotonic, binary search the capacity range [max, sum] for the smallest feasible value. If mid needs no more than days days, it might be the answer, so hi = mid; otherwise lo = mid + 1. This takes O(log(sum - max)) feasibility checks, each O(n).

For [3,2,2,4,1,4] and 3 days the range is [4, 16]:

lo	hi	mid	days needed at mid	action
4	16	10	2 (`[3,2,2]`, `[4,1,4]`)	fits, hi = 10
4	10	7	3 (`[3,2,2]`, `[4,1]`, `[4]`)	fits, hi = 7
4	7	5	4 (`[3,2]`, `[2]`, `[4,1]`, `[4]`)	too slow, lo = 6
6	7	6	3 (`[3,2]`, `[2,4]`, `[1,4]`)	fits, hi = 6

The range collapses to 6.

Java

public class Main {
    static class Solution {
        private int daysNeeded(int[] weights, int capacity) {
            int days = 1;
            int load = 0;
            for (int w : weights) {
                if (load + w > capacity) {
                    days++;
                    load = 0;
                }
                load += w;
            }
            return days;
        }

        public int shipWithinDays(int[] weights, int days) {
            if (weights.length == 0) {
                return 0;
            }
            int lo = 0, hi = 0;
            for (int w : weights) {
                lo = Math.max(lo, w);
                hi += w;
            }
            while (lo < hi) {
                int mid = lo + (hi - lo) / 2;
                if (daysNeeded(weights, mid) <= days) {
                    hi = mid;
                } else {
                    lo = mid + 1;
                }
            }
            return lo;
        }
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.shipWithinDays(new int[] {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, 5));
        System.out.println(s.shipWithinDays(new int[] {3, 2, 2, 4, 1, 4}, 3));
        System.out.println(s.shipWithinDays(new int[] {1, 2, 3, 1, 1}, 4));
        System.out.println(s.shipWithinDays(new int[] {}, 3));
    }
}

Output

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