Solution Explanation: Boats to Save People

This problem can be efficiently solved using a greedy approach with two pointers. The core idea is to minimize the number of boats used by optimally pairing lighter and heavier people whenever possible.

Algorithm:

1. Sort: Sort the people array in ascending order of their weights. This allows us to efficiently pair lighter and heavier people.

2. Two Pointers: Initialize two pointers, left and right, pointing to the beginning and end of the sorted people array, respectively. left represents the lightest person, and right represents the heaviest.

3. Iteration: Iterate while left is less than or equal to right:

   • Pair Check: Check if the sum of weights of the lightest person (people[left]) and the heaviest person (people[right]) is less than or equal to the limit.
     • If people[left] + people[right] <= limit: This means we can put both people in the same boat. Increment left (move to the next lightest person) and decrement right (move to the next heaviest person).
     • If people[left] + people[right] > limit: This means the heaviest person (people[right]) needs a boat by themselves. Only decrement right.

4. Boat Count: Increment the ans (boat count) in each iteration. This represents using one boat in each step.

5. Return: After the loop finishes, ans contains the minimum number of boats needed.

Time Complexity: O(n log n), dominated by the sorting step.

Space Complexity: O(log n) or O(1), depending on the sorting implementation. In-place sorting algorithms like quicksort or mergesort use logarithmic space for the recursive calls.

Code Implementation (Python):

class Solution:
    def numRescueBoats(self, people: List[int], limit: int) -> int:
        people.sort() #Sort the people by weight
        left = 0
        right = len(people) - 1
        ans = 0
        while left <= right:
            if people[left] + people[right] <= limit:
                left += 1 #Both people fit in one boat
            right -= 1 #Heaviest person always needs a boat, might be alone
            ans += 1
        return ans

Code Implementation (Java):

import java.util.Arrays;
 
class Solution {
    public int numRescueBoats(int[] people, int limit) {
        Arrays.sort(people); //Sort people array
        int left = 0;
        int right = people.length - 1;
        int ans = 0;
        while (left <= right) {
            if (people[left] + people[right] <= limit) {
                left++; //Both fit in one boat
            }
            right--; //Heaviest person always needs a boat
            ans++;
        }
        return ans;
    }
}

Code Implementation (C++):

#include <algorithm>
#include <vector>
 
class Solution {
public:
    int numRescueBoats(vector<int>& people, int limit) {
        std::sort(people.begin(), people.end()); //Sort people vector
        int left = 0;
        int right = people.size() - 1;
        int ans = 0;
        while (left <= right) {
            if (people[left] + people[right] <= limit) {
                left++; //Both fit in one boat
            }
            right--; //Heaviest person needs a boat
            ans++;
        }
        return ans;
    }
};

The other languages (Go, TypeScript) would follow similar structures, employing sorting and a two-pointer approach for optimal boat usage. The core logic remains consistent across all the languages.