Loading
Loading
A trekking group must cross a lake in inflatable rafts. Each raft carries at most two hikers, and their combined weight may not exceed limit. Every hiker weighs no more than the limit on their own.
Return the fewest rafts needed to get the whole group across (each raft crosses once).
weights = [3, 5, 3, 4], limit = 5sorted: 3 3 4 5lightest at the left, heaviest at the right5 + 3 > 55 rides alone (raft 1)4 + 3 > 54 rides alone (raft 2)3 + 3 > 53 alone (raft 3), last 3 alone (raft 4)4Sign in to keep a note here. It is free, and nobody else can see it.
Sign inExample 1
Both hikers fit on one raft: 1 + 2 = 3.
Example 2
Sign in to open hints.
Struggling is where the learning happens. Open this once you have genuinely tried, or once the hints have run out.
O(n log n) time · O(n) space
Input. Run your code to watch it work on this input, one line at a time.
Running code is turned off on this deployment. You can still read the problem, write code, use hints and the visualizer.
Tab moves focus out of the editor. Press Ctrl+M to let Tab indent instead.
No results yet
Run your code against the sample tests, or submit to run the full suite.
No two hikers fit together under 5, so each needs a raft.