Editorial for Boat

Approach

Sort the weights.

We always place the heaviest remaining person into a new boat. To use as few boats as possible, we should try to pair them with the lightest remaining person who still fits. If even the lightest person is too heavy, then the heaviest person must go alone.

After sorting, this is easy with two pointers:

• Let $left$ point to the lightest remaining person.
• Let $right$ point to the heaviest remaining person.
• Use one boat for the person at position $right$.
• If $\text{weights}[left] + \text{weights}[right] \le x$, put both in that boat and move $left$.
• Always move $right$, because the heaviest person has now been assigned.

This greedy choice is optimal because pairing the heaviest person with any heavier partner would only make fitting harder, and leaving a lighter person unused when they could fit cannot help later.

The time complexity is $O(n \log n)$ because of sorting.

Solution (Python)

import sys

input = sys.stdin.readline

n, x = map(int, input().split())
weights = list(map(int, input().split()))

weights.sort()

left = 0
right = n - 1
boats = 0

while left <= right:
    boats += 1
    if weights[left] + weights[right] <= x:
        left += 1
    right -= 1

print(boats)