Ship Packages Within Days

Problem

Given package weights in order and a number of days, return the minimum ship capacity that ships all packages within the days while preserving order. Assume days >= len(weights).

Binary search the capacity between the heaviest package and the total weight, greedily loading packages until the next one would overflow into a new day.

Hint

The capacity can never be smaller than the heaviest single package.

Test cases

case 1

in: [[1,2,3,4,5,6,7,8,9,10],5]

expected: 15

case 2

in: [[3,2,2,4,1,4],3]

expected: 6

case 3

in: [[1,2,3,1,1],4]

expected: 3

case 4

in: [[1],1]

expected: 1

case 5

in: [[10],5]

expected: 10

Starter codePython

def ship_within_days(weights, days):
    # Your code here
    pass

5 test cases · run your code against them in the editor