Capacity To Ship Packages Within D Days Visualizer & Step-by-Step Algorithm Solution

Binary search on candidate ship capacity in range [max(weights) .. sum(weights)] to find minimum capacity feasible within D days.

Category: binary-search | Difficulty: Medium

Tags: Binary Search on Answer, Greedy Simulation

Capacity To Ship Packages Within D Days

Package Weights
1
0
2
1
3
2
4
3
5
4
6
5
7
6
8
7
9
8
10
9
L
10
R
55
100%
state
allowed days5
total weight55
Initialization
1/91
Explanation

Start shipWithinDays() with 10 packages to ship in at most 5 days.

Source Code
1function shipWithinDays(weights, days) {
2 let left = Math.max(...weights);
3 let right = weights.reduce((a, b) => a + b, 0);
4 while (left < right) {
5 const mid = Math.floor((left + right) / 2);
6 const reqDays = getDaysNeeded(weights, mid);
7 if (reqDays > days) {
8 left = mid + 1;
9 } else {
10 right = mid;
11 }
12 }
13 return left;
14}
15function getDaysNeeded(weights, cap) {
16 let days = 1, currentLoad = 0;
17 for (const w of weights) {
18 if (currentLoad + w > cap) {
19 days++; currentLoad = 0;
20 }
21 currentLoad += w;
22 }
23 return days;
24}