AlgoViz
HomeBinary Search

Capacity to Ship Packages Within D Days

Medium

Binary search the ship's capacity

Problem

You are given an array weights where weights[i] represents the weight of the i-th package on a conveyor belt. All the packages must be shipped in the order given from one port to another within days days. Each day, the ship can carry a contiguous sequence of packages, as long as the total weight does not exceed its maximum capacity. Your task is to find the minimum possible capacity of the ship so that all packages can be shipped within the given number of days.

In simple words

More capacity means fewer days — binary-search the smallest ship that still finishes in time.

The idea

A bigger ship never needs more days, so 'can we finish within d days at capacity c?' is monotone in c. Binary search c between the heaviest single package and the total weight, testing each candidate with a greedy O(n) simulation.

The trick

  • Lower bound is max(weights) — the ship must fit the biggest package.
  • Upper bound is sum(weights) — one day.
  • The feasibility check is a simple greedy pass, so the whole thing is O(n log sum).
5
6
7
8
9
10
11
12
13
14
15
0
1
2
3
4
5
6
7
8
9
10
candidates11

Step 1 of 4. Brute force: try every ship capacity until the load fits in 3 days. Values: 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15. candidates 11.

1/4
Brute force
timeO(sum·n)spaceO(1)

Try every capacity.

1// try every ship capacity from max weight up2for (let cap = maxW; cap <= sum; cap++)3  if (daysNeeded(cap) <= days) return cap;4return sum;

Input

array
[5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]

Memory

try
—
candidates
11
capacity
—

Output

capacity
—
answer
—

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:
weights = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], days = 5
Output:
15
Explanation:
A ship of size 15 finishes in 5 days.

Example 2

Input:
weights = [3, 2, 2, 4, 1, 4], days = 3
Output:
6
Explanation:
Capacity 6 splits the load into 3 days.

Example 3

Input:
weights = [1, 2, 3, 1, 1], days = 4
Output:
3
Explanation:
Capacity 3 fits in 4 days.

Constraints

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

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.