Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

Mediumbinary-search-on-answer

Capacity To Ship Packages Within D Days

Problem (restated)

Packages must ship in order within days days. Find the least weight capacity of the ship that makes this possible.

Intuition

Feasibility is monotonic in capacity: if C works, C+1 works. Binary search the capacity.

Approaches

Binary search on capacity

Unverified

Time O(n log S)Space O(1)

Idea. lo = max(weights), hi = sum(weights). For mid capacity, greedy-count days needed.

Walkthrough. weights=[1,2,3,4,5,6,7,8,9,10], days=5 → answer 15.

Trade-offs. Same pattern as Koko; define a clear canShip(cap) predicate.

Solution

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

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

Template connection

Binary search on ship capacity; greedy day-count is the feasibility check.

Reflection

Same skeleton as Koko: binary-search the capacity, and feasible counts days without reordering the packages.
lo is max(weights), so one package fits. hi is the sum of the weights.
The package order is fixed. Reordering is not legal.