Solution
Approach 1: Greedy (Two Pointer)
Intuition
If the heaviest person can share a boat with the lightest person, then do so. Otherwise, the heaviest person can't pair with anyone, so they get their own boat.
The reason this works is because if the lightest person can pair with anyone, they might as well pair with the heaviest person.
Algorithm
Let people[i]
to the currently lightest person, and people[j]
to the heaviest.
Then, as described above, if the heaviest person can share a boat with the lightest person (if people[j] + people[i] <= limit
) then do so; otherwise, the heaviest person sits in their own boat.
Complexity Analysis

Time Complexity: , where is the length of
people
. 
Space Complexity: .
Analysis written by: @awice.