Skip to main content

19. Capacity to Ship Packages Within D Days

mediumAsked at JetBrains

Find the minimum daily ship capacity to deliver all packages within D days — JetBrains uses this to test binary-search-on-answer, the technique behind their build-time autotuner.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Given an array of package weights to ship in order and a number of days, return the minimum daily capacity that lets you ship them all within days. You must ship packages in the given order.

Constraints

  • 1 <= days <= weights.length <= 5 * 10^4
  • 1 <= weights[i] <= 500

Examples

Example 1

Input
weights=[1,2,3,4,5,6,7,8,9,10], days=5
Output
15

Example 2

Input
weights=[3,2,2,4,1,4], days=3
Output
6

Approaches

1. Linear search over capacity

Try every capacity from max(weights) upward until the simulation finishes in time.

Time
O(sum * n)
Space
O(1)
for (let cap=Math.max(...w); ; cap++) if (canShip(w, days, cap)) return cap;

Tradeoff:

2. Binary search on capacity

Lower bound is max(weights), upper bound is sum(weights). Binary-search the smallest capacity for which simulation fits within days. Same answer-space binary search JetBrains uses to tune budget thresholds.

Time
O(n log sum)
Space
O(1)
function shipWithinDays(weights, days) {
  let lo = Math.max(...weights), hi = weights.reduce((a, b) => a + b, 0);
  const canShip = (cap) => {
    let used = 1, load = 0;
    for (const w of weights) {
      if (load + w > cap) { used++; load = 0; }
      load += w;
    }
    return used <= days;
  };
  while (lo < hi) {
    const mid = (lo + hi) >> 1;
    if (canShip(mid)) hi = mid; else lo = mid + 1;
  }
  return lo;
}

Tradeoff:

JetBrains-specific tips

JetBrains expects you to name 'binary search on the answer' explicitly — the same shape autotuners use when tuning indexing budgets against latency SLAs.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

Drill Capacity to Ship Packages Within D Days and other JetBrains interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →