Capacity To Ship Packages Within D Days

Medium

Problem

Packages must be shipped in the given order. Each day the ship carries a prefix of the remaining packages, with total weight at most its capacity. Return the minimum capacity that ships everything within days days.

Example 1

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

[1–5], [6, 7], [8], [9], [10].

Test cases

Case 1

Input:    [1,2,3,4,5,6,7,8,9,10], 5
Expected: 15

Case 2

Input:    [3,2,2,4,1,4], 3
Expected: 6

Case 3

Input:    [1,2,3,1,1], 4
Expected: 3

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. Binary search on capacity + greedy check

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

Capacity lies between the heaviest package and the total weight. For a guess, greedily fill each day and count days.

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