Boats to Save People [Medium] — Greedy Two Pointers Sort

Problem Statement

Each boat can carry at most 2 people with total weight <= limit. Return the minimum number of boats required.

Input: people=[1,2], limit=3 → Output: 1
Input: people=[3,2,2,1], limit=3 → Output: 3
Input: people=[3,5,3,4], limit=5 → Output: 4

Intuition

Sort and use two pointers. Try to pair the lightest with the heaviest. If they fit, take both (l++, r--). Otherwise, heaviest goes alone (r--).

Solutions

C++

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

Java

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

JavaScript

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

Python

def numRescueBoats(people: list[int], limit: int) -> int:
    people.sort()
    l, r, boats = 0, len(people)-1, 0
    while l <= r:
        if people[l] + people[r] <= limit:
            l += 1
        r -= 1
        boats += 1
    return boats

Complexity

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