Capacity To Ship Packages Within D Days
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
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;}