codejump
MediumPro challengePythonJavaScriptTypeScript

Binary Search — Capacity to Ship Packages

AlgorithmsBinary SearchBinary Search on AnswerGreedy

solve(weights, days) — packages must be shipped in the given order, one ship
load per day, and a day's load is a consecutive run of packages whose total weight
cannot exceed the ship's capacity. Return the least capacity that ships everything
within days days.

Binary search the *answer*: the capacity is at least max(weights) (the heaviest
package must fit) and at most sum(weights) (everything in one day). For a candidate
capacity, a greedy pass counts the days needed. "Fits in days days" is false for
small capacities and true from some point on.

Examples

solve([1,2,3,4,5,6,7,8,9,10], 5)  → 15
solve([3,2,2,4,1,4], 3)           → 6
solve([1,2,3,1,1], 4)             → 3

Sample tests

Test #1Classic example
Input: [[1,2,3,4,5,6,7,8,9,10],5]
Output: 15
Test #2Second example
Input: [[3,2,2,4,1,4],3]
Output: 6
Test #3Heaviest package sets the bound
Input: [[1,2,3,1,1],4]
Output: 3
← All challenges