Capacity To Ship Packages Within D Days

Binary search on the ship capacity itself: a greedy pass counts the days a capacity needs, and more capacity never needs more days.

The idea

The answer lies between the heaviest package (anything smaller cannot carry it) and the total weight (one day carries everything). For a given capacity, loading greedily in order (keep adding until the next package would not fit, then start a new day) uses the fewest days possible. A bigger ship never needs more days, so the capacities split into "too small" then "big enough", and binary search finds the first big-enough one.

Code

public int ShipWithinDays(int[] weights, int days) {
    int lo = weights.Max(), hi = weights.Sum();
    while (lo < hi) {
        int cap = lo + (hi - lo) / 2;
        if (DaysNeeded(weights, cap) <= days) hi = cap;
        else lo = cap + 1;
    }
    return lo;
}

static int DaysNeeded(int[] weights, int cap) {
    int days = 1, load = 0;
    foreach (int w in weights) {
        if (load + w > cap) { days++; load = 0; } // ship is full: w waits for the next day
        load += w;
    }
    return days;
}

Tips

• Greedy filling is optimal for a fixed capacity: sending a ship off early can only push packages later, never save a day.
• Big enough: hi = cap, because cap itself may be the answer. Too small: lo = cap + 1.
• Same pattern as Koko Eating Bananas and Split Array Largest Sum: binary search on the answer, check each guess with a linear pass.

In the .NET library

weights.Max() and weights.Sum() need using System.Linq. Enumerable.Sum on int[] throws OverflowException rather than wrapping, so for huge inputs sum into a long.