Boats to Save People

Problem Statement

Each boat carries at most two people and a total weight of at most limit. Given people’s weights, return the minimum number of boats needed.

Example

Input:  people = [3,2,2,1], limit = 3
Output: 3
Explanation: (1,2), (2), (3).

Two Pointer Approach

Sort the weights. Pair the lightest and heaviest with two pointers: if they fit together, send both; otherwise the heaviest goes alone. Each step uses exactly one boat.

Complexity

• Time: O(n log n)
• Space: O(1) extra

Solution Code

Python

def numRescueBoats(people, limit):
    people.sort()
    left, right = 0, len(people) - 1
    boats = 0
    while left <= right:
        if people[left] + people[right] <= limit:
            left += 1
        right -= 1
        boats += 1
    return boats

Java

int numRescueBoats(int[] people, int limit) {
    Arrays.sort(people);
    int left = 0, right = people.length - 1, boats = 0;
    while (left <= right) {
        if (people[left] + people[right] <= limit) left++;
        right--;
        boats++;
    }
    return boats;
}

C++

int numRescueBoats(vector<int>& people, int limit) {
    sort(people.begin(), people.end());
    int left = 0, right = people.size() - 1, boats = 0;
    while (left <= right) {
        if (people[left] + people[right] <= limit) left++;
        right--;
        boats++;
    }
    return boats;
}

Key Takeaways

• Greedy pairing of lightest + heaviest is provably optimal here.
• The heaviest person always leaves on the current boat.
• Sorting enables the two pointer sweep.