FunctionRacerProblemsRace

Least Truck Capacity

MediumSorting and searchingPython, JavaScript, TypeScript, Java, C++

A truck must deliver the packages with weights weights, in the given order, using at most trips trips. On each trip it loads the next packages in order, as many as fit, as long as their total weight does not exceed its capacity; it never splits a package or changes the order.

Return the smallest capacity that lets the truck deliver everything in trips trips or fewer. The capacity must be at least the heaviest package. Binary search over the capacity works: for a candidate, count the trips greedily and check whether they fit.

Example 1

weights [3,2,2,4,1,4]
trips 3
returns 6

With capacity 6 the trips carry [3, 2], [2, 4] and [1, 4]; with capacity 5 four trips are needed.

Example 2

weights [1,2,3,4,5,6,7,8,9,10]
trips 5
returns 15

Capacity 15 gives the trips [1, 2, 3, 4, 5], [6, 7], [8], [9] and [10]; capacity 14 would need six.

Constraints

Race itor take your time

Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.

More Sorting and searching problems