LC881. Boats to Save People

Approach 1: Two-Pointer (Greedy)

class Solution:
    def numRescueBoats(self, people: List[int], limit: int) -> int:
        people.sort()
        
        min_boats = 0
        l, r = 0, len(people) - 1
 
        while l <= r:
            if l != r and people[l] + people[r] <= limit:
                l += 1
                r -= 1
            else:
                r -= 1
 
            min_boats += 1
        
        return min_boats

Complexity

Time: $O(nlogn)$
Space: $O(1)$

Notes

Other Languages

Go

import "slices"
 
func numRescueBoats(people []int, limit int) int {
    slices.Sort(people)
    l, r := 0, len(people) - 1
    min_boats := 0
 
    for l <= r {
        if l != r && people[l] + people[r] <= limit {
            l++
        }
 
        r--
        min_boats++
    }
 
    return min_boats
}