Skip to main content

881. Boats to Save People

https://leetcode.com/problems/boats-to-save-people/

Level: Medium

Topics: Greedy, Two Pointers, Sort

After sort, everything is clear. We can use two pointers to solve this problem.

But if the max people that can get on a boat is 3 or more, this will be more complicated.

Initial Solution​

class Solution:
    def numRescueBoats(self, people: List[int], limit: int) -> int:
        people.sort()
        p1, p2 = 0, len(people) - 1
        boat = 0
        while p1 < p2:
            if people[p1] + people[p2] <= limit:
                p1 += 1
                p2 -= 1
                boat += 1
            else:
                p2 -= 1
                boat += 1
        if p1 == p2:
            boat += 1
        return boat

Optimized Solution​

class Solution:
    def numRescueBoats(self, people: List[int], limit: int) -> int:
        people.sort()
        boat, p1, p2 = 0, 0, len(people) - 1
        while p1 <= p2:
            if people[p1] + people[p2] <= limit:
                p1 += 1
            p2 -= 1
            boat += 1
        return boat