FunctionRacerProblemsRace

Fewest Ferry Crossings

HardDynamic programmingPython, JavaScript, TypeScript, Java, C++

A ferry carries at most limit kilograms on each crossing. Crate i weighs crates[i] kilograms, and no crate is heavier than limit. A crossing can carry any group of crates whose weights add up to at most limit; crates cannot be split.

Return the fewest crossings needed to carry every crate. With no crates, return 0.

Example 1

crates [2,7,4,2,3,3,2]
limit 8
returns 3

Send the 7 alone, then 4 + 2 + 2 and 3 + 3 + 2, both exactly 8 kilograms. Loading the heaviest crates first would need four crossings.

Example 2

crates [6,6,6]
limit 10
returns 3

No two crates fit together, so each needs its own crossing, even though the total is only 18.

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 Dynamic programming problems