610. Fewest Boats to Carry Everyone
Each person has a weight, and every boat carries AT MOST TWO people whose weights together
are at most limit. Every weight is at most limit, so everyone can travel.
Print the fewest boats needed to carry everyone.
weights 1 2, limit 3 -> 1 both in one boat
weights 3 2 2 1, limit 3 -> 3
## The rule
Sort. Put the lightest and the heaviest together if they fit; otherwise the heaviest travels alone. Either way the heaviest leaves on this boat.
i = 0, j = n-1, boats = 0
while i <= j:
if a[i] + a[j] <= limit: i += 1
j -= 1
boats += 1
Note that j moves and boats increases on EVERY iteration, because the heaviest remaining
person always departs. Only i is conditional.
## Why the sweep is optimal
A boat carries one or two people, so
boats = n - (number of pairs formed)
and maximising pairs is the whole problem. Two cases, taking a[i] as the lightest person
left and a[j] as the heaviest.
CASE 1: a[i] + a[j] > limit. Then a[j] can pair with nobody remaining, because a[i] is
the lightest candidate there is and even that does not fit. So a[j] sails alone in EVERY
solution. That is forced, not chosen, and removing them leaves the same problem on fewer
people.
CASE 2: a[i] + a[j] <= limit. Then some optimal solution pairs them. Take any optimal
solution and look at what it does with i and j:
· both alone: pairing them adds a pair, so the solution was not optimal
· i with p, j alone: swap to i with j, and p alone. Legal, same pair count
· i alone, j with q: swap to i with j, and q alone. Legal, same pair count
· i with p, j with q: swap to (i, j) and (p, q). The first fits by assumption.
The second fits because a[p] <= a[j], since j is the heaviest, so
a[p] + a[q] <= a[j] + a[q] <= limit. Same pair count
In every case there is an optimal solution pairing them, so taking that pair loses nothing. Remove both and repeat.
That last bullet is the one carrying the weight, and it is why the sweep pairs the LIGHTEST with the heaviest rather than any other fitting partner.
## Boundaries
One person needs one boat. If nobody can share, the answer is n.
2 2 2 2 with limit 3 answers 4: no two of them fit together.
1 1 1 with limit 2 answers 2: one pair and one alone, so the answer is not ceil(n/2) by
accident but by the pairing.
## Cost
Time O(n log n) for the sort. Space O(1) beyond the input.
Constraints - `1 ≤ n ≤ 200000` - `1 ≤ each weight ≤ limit ≤ 10^9`
Input
The first line contains two integers n and limit.
The second line contains n integers, the weights.
Output
Print one integer, the fewest boats needed.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.