539. Boats to Save People
An evacuation is underway. You are given an array people, where people[i] is the weight of person i, and an integer limit — the weight capacity shared by every rescue boat.
Each boat seats at most two passengers at a time, and a boat may only launch if its passengers' combined weight is at most limit. Every individual weighs no more than limit, so anyone can ride alone.
Your function receives people and limit and returns the minimum number of boats required to carry everyone.
Example 1:
Input: people = [1, 2], limit = 3
Output: 1
Explanation: Both people together weigh 1 + 2 = 3, which fits within the limit, so a single boat carries them both.
Example 2:
Input: people = [3, 2, 2, 1], limit = 3
Output: 3
Explanation: One boat takes the pair (1, 2); the remaining 2 and the 3 each need their own boat, since any pairing with them exceeds the limit of 3.
Constraints:
- 1 ≤ people.length ≤ 5 * 10⁴
- 1 ≤ people[i] ≤ limit ≤ 3 * 10⁴
Hints:
Sort first. The heaviest person must board some boat — who is the only person ever worth seating beside them?
Keep one pointer at the light end and one at the heavy end of the sorted array. Each iteration launches exactly one boat: the heavy person always boards, and the light person hops in too only when the pair fits under the limit.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: people = [1, 2], limit = 3
Expected output: 1