Approach 1: Greedy (Two Pointer)
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.
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.
Time Complexity: , where is the length of
Space Complexity: .
Analysis written by: @awice.