Capacity To Ship Packages Within D Days

medium array binary search answer search

Problem

Given weights[i] for packages to be shipped in order, find the minimum ship capacity that lets all of them be delivered within D days. Packages must keep their original order and a single ship runs once per day.

Inputweights = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], days = 5

Output15

Split as [1,2,3,4,5] [6,7] [8] [9] [10] — five days, max load 15.

weights (comma-separated)

days

def shipWithinDays(weights, days):
    def needed(cap):
        d, load = 1, 0
        for w in weights:
            if load + w > cap:
                d += 1
                load = 0
            load += w
        return d
    lo, hi = max(weights), sum(weights)
    while lo < hi:
        mid = (lo + hi) // 2
        if needed(mid) <= days:
            hi = mid
        else:
            lo = mid + 1
    return lo

function shipWithinDays(weights, days) {
  const needed = (cap) => {
    let d = 1, load = 0;
    for (const w of weights) {
      if (load + w > cap) { d++; load = 0; }
      load += w;
    }
    return d;
  };
  let lo = Math.max(...weights), hi = weights.reduce((a,b)=>a+b,0);
  while (lo < hi) {
    const mid = (lo + hi) >> 1;
    if (needed(mid) <= days) hi = mid;
    else lo = mid + 1;
  }
  return lo;
}

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) >>> 1;
            if (needed(weights, mid) <= days) hi = mid;
            else lo = mid + 1;
        }
        return lo;
    }
    private int needed(int[] w, int cap) {
        int d = 1, load = 0;
        for (int x : w) {
            if (load + x > cap) { d++; load = 0; }
            load += x;
        }
        return d;
    }
}

class Solution {
public:
    int shipWithinDays(vector<int>& w, int days) {
        int lo = 0, hi = 0;
        for (int x : w) { lo = max(lo, x); hi += x; }
        auto needed = [&](int cap) {
            int d = 1, load = 0;
            for (int x : w) {
                if (load + x > cap) { d++; load = 0; }
                load += x;
            }
            return d;
        };
        while (lo < hi) {
            int mid = (lo + hi) / 2;
            if (needed(mid) <= days) hi = mid;
            else lo = mid + 1;
        }
        return lo;
    }
};

Explanation

This is a classic binary search on the answer. We are not searching inside the array — we are searching over the possible ship capacities to find the smallest one that still finishes within days.

The trick is that capacity has a clean cutoff: if some capacity works, every larger capacity also works. So we can binary-search. The smallest sensible capacity is max(weights) (the ship must at least carry the heaviest package), and the largest is sum(weights) (everything in one day).

For a candidate capacity, the helper needed(cap) does a greedy day count: walk the weights in order, keep adding to the current day's load, and start a new day whenever the next package would overflow cap. It returns how many days that takes.

If needed(mid) <= days the capacity is enough, so we try smaller with hi = mid; otherwise we need a bigger ship, so lo = mid + 1. When lo meets hi, that value is the minimum capacity.

Example: weights = [1..10], days = 5. Capacity 15 splits the run into [1,2,3,4,5] [6,7] [8] [9] [10] — five days — and nothing smaller does, so the answer is 15.

Time: O(n log S) where S = sum of weights Space: O(1)