Problem Description

The "Boats to Save People" problem asks you to determine the minimum number of boats required to rescue all people, given certain constraints. Each person has a specific weight, represented as an integer in the people array. Each boat can carry at most two people at the same time, provided the sum of their weights does not exceed the boat's weight limit, given as limit. Every person must be rescued, and each person can be assigned to only one boat (no reuse).

Your task is to return the minimum number of boats needed to save everyone.

• Each boat can carry at most two people.
• The combined weight of people in a boat cannot exceed limit.
• Each person can be rescued only once.
• There is always at least one valid solution.

Thought Process

The first instinct might be to try every possible combination of people to fit into boats, but this would be too slow for large inputs. Instead, we can look for ways to pair up people efficiently so that as many boats as possible carry two people, minimizing the total number of boats.

A key insight is that pairing the lightest person with the heaviest person (when possible) will often maximize boat utilization. If the heaviest person cannot be paired with the lightest, then the heaviest person must go alone. This leads to a two-pointer strategy, which is much faster than checking all possible pairs.

Solution Approach

Here’s a step-by-step breakdown of the optimized algorithm:

1. Sort the people array: This allows us to efficiently pair the lightest and heaviest people.
2. Use two pointers:
   • One pointer (i) starts at the beginning (lightest person).
   • The other pointer (j) starts at the end (heaviest person).
3. Iterate while i <= j:
   • If the sum of weights at i and j is less than or equal to limit, pair them together in one boat and move both pointers inward (i++, j--).
   • If not, the heavier person at j must go alone, so just move j--.
   • In both cases, increment the boat count.
4. Repeat until all people are assigned to boats.

This approach ensures we use the fewest boats possible by always trying to fit two people per boat when feasible.

Example Walkthrough

Let’s consider the example: people = [3, 2, 2, 1], limit = 3.

1. Sort people: [1, 2, 2, 3]
2. Initialize i = 0 (points to 1), j = 3 (points to 3), boats = 0.
3. First iteration:
   • 1 (i) + 3 (j) = 4 > 3, so 3 goes alone. Move j to 2. Boats = 1.
4. Second iteration:
   • 1 (i) + 2 (j) = 3 ≤ 3, so pair 1 and 2. Move i to 1, j to 1. Boats = 2.
5. Third iteration:
   • 2 (i) alone (since i == j). Boats = 3.
6. All people are assigned: answer is 3 boats.

Time and Space Complexity

• Brute-force approach: Would check all possible pairings, leading to exponential time complexity (O(2ⁿ)), which is infeasible for large n.
• Optimized two-pointer approach:
  • Time complexity: Sorting the array takes O(n log n), and the two-pointer scan is O(n). So, the overall time is O(n log n).
  • Space complexity: O(1) extra space (if sorting in-place), or O(n) if sorting creates a copy.

Summary

The "Boats to Save People" problem is elegantly solved by sorting the people by weight and using a two-pointer approach to pair the lightest and heaviest people wherever possible. This strategy ensures that we use the minimum number of boats by maximizing boat utilization, and it runs efficiently even for large input sizes.

Code Implementation

class Solution:
    def numRescueBoats(self, people, limit):
        people.sort()
        i, j = 0, len(people) - 1
        boats = 0
        while i <= j:
            if people[i] + people[j] <= limit:
                i += 1
            j -= 1
            boats += 1
        return boats
      

class Solution {
public:
    int numRescueBoats(vector<int>& people, int limit) {
        sort(people.begin(), people.end());
        int i = 0, j = people.size() - 1, boats = 0;
        while (i <= j) {
            if (people[i] + people[j] <= limit) {
                i++;
            }
            j--;
            boats++;
        }
        return boats;
    }
};
      

class Solution {
    public int numRescueBoats(int[] people, int limit) {
        Arrays.sort(people);
        int i = 0, j = people.length - 1, boats = 0;
        while (i <= j) {
            if (people[i] + people[j] <= limit) {
                i++;
            }
            j--;
            boats++;
        }
        return boats;
    }
}
      

var numRescueBoats = function(people, limit) {
    people.sort((a, b) => a - b);
    let i = 0, j = people.length - 1, boats = 0;
    while (i <= j) {
        if (people[i] + people[j] <= limit) {
            i++;
        }
        j--;
        boats++;
    }
    return boats;
};