Shipping Packages in D Days: Finding Minimum Capacity

You have to ship packages with weights weight[i] each day in order. You need to do this in D days. What’s the minimum capacity your conveyor belt needs?

The minimum capacity is the heaviest single package. That’s because you must ship it alone. The maximum capacity is the sum of all weights. This happens when D equals 1.

We have a continuous range to search. Binary search cuts down the search space dramatically. We pick a middle capacity. If the shipping takes more than D days, our capacity is too small. If it takes fewer days, our capacity is too big.

int shipWithinDays(vector<int>& weights, int D) {
    int max=weights[0];
    int sum=0;
    for(auto n : weights) {
        if (n>max) max=n;
        sum+=n;
    }

    int start=max;
    int end=sum;
    while(start<end) {
        int mid=(start+end)>>1;
        int ds=ship(weights, mid, D);
        if (ds > 0) start=mid+1;
        else end=mid;
    }
    return start;
}

int ship(vector<int> &w, int cap, int d, int cur=0, int curd=1) {
    for(auto n : w) {
        cur+=n;
        if (cur>cap) {
            cur=n;
            ++curd;
            // End early if we exceed D days
            if (curd>d) return 1;
        }
    }
    return curd-d;
}

This cuts the problem from O(n * total_weight) to O(n * log(total_weight)). Much faster when the weight sum gets large.

#binary-search