# Leetcode 881: Boats to save people

## Desciption

You are given an array `people` where `people[i]` is the weight of the `i-th` person, and an infinite number of boats where each boat can carry a maximum weight of `limit`. Each boat carries at most two people at the same time, provided the sum of the weight of those people is at most `limit`.

Return the minimum number of boats to carry every given person.

For example:
> people = [4, 5, 3, 1]
> limit = 8
> ans = 2 ((5, 3) and (4, 1))

## Analysis
Consider the people w/ **largest weight**. (say it has weight `M`).

### case 1
If `M` + `a` > `limit` (where `a` is weight of any person), then he must occupy a boat by himself.

### case 2
Let's say `M`+`m` < `limit`, `m` is the weight of lightest person.
Can we greedily pair `M` and `m` together, and do the same with the rest of the people ?

Consider in an optimal solution, `M` is paired with `p`, and `m` with `q`.
Clearly,

m <= p, q <= M
m+q <= limit
p+M <= limit

Notice that `p+q <= p+M <= limit`, thus `(p, q)` is also a valid pair.
Also since `m+M <= limit`, so we can safely swap the pairs:

(m, q), (p, M) -> (m, M), (p, q)

without changing the optimality.

## Algorithm
The idea is the same in the Analysis above, keep pairing the largest w/ the smallest. If cannot pair, place it singly in a boat.

n = len(people)
ans = 0

sort(people)

l, r = 0, n-1
while l < r:
    if people[l]+people[r] <= limit:
        l++
    r--
    ans++
return ans

###### tags: `Leetcode`