324. Capacity to Ship Packages Within D Days

If capacity C works, any C' > C works too. Binary-search the smallest feasible C. The search range is [max(weights), sum(weights)] — we need to fit the heaviest package in one trip, and the trivial upper bound is shipping everything in one day.

Approach

1. Feasibility canShip(C): greedily fill each day until weight would exceed C, then start a new day. Return whether day count <= days.
2. Binary search over [max(weights), sum(weights)].

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

    private boolean canShip(int[] weights, int days, int cap) {
        int used = 1, cur = 0;
        for (int w : weights) {
            if (cur + w > cap) {
                used++;
                cur = 0;
            }
            cur += w;
        }
        return used <= days;
    }
}