A lake tour company has n tourists signed up, each with a known weight. Each kayak can carry at most 2 tourists at a time, and the combined weight of the tourists in a kayak must not exceed a limit W. Every individual tourist's weight is guaranteed to not exceed W on its own. Find the minimum number of kayaks needed to take every tourist out on the lake (a kayak may also carry just 1 tourist if it cannot be paired).
Line 1: two integers n W.
Line 2: n space-separated integers, the tourists' weights.
A single integer: the minimum number of kayaks needed.
Example 1
Input
4 100 70 50 80 40
Expected
3
Explanation
Sorted weights [40, 50, 70, 80], each kayak carrying at most two people with combined weight <= 100. Pair the lightest with the heaviest that fits: 40+80=120 and 40+70=110 both exceed 100, so 80 and 70 each ride alone; the remaining 40+50=90 shares one kayak. That is 3 kayaks, the fewest possible.
Example 2
Input
3 10 4 5 6
Expected
2
Explanation
Sorted weights [4,5,6] with limit 10: pair the lightest (4) and heaviest (6): 4+6=10, fits. Remaining tourist (5) takes a kayak alone. Total: 2 kayaks.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →