Problem Statement in English

You’re given a list of people’s weights, and a boat can carry at most limit weight at a time. Each person can be transported by a boat, and each boat can carry at most 2 people at a time.

Your task is to return the minimum amount number of boats required to save all people.

Approach

What you have to realize here is that if the heaviest person (let’s call them H) can’t go with the lightest person, then H can’t go with anyone else either, and so, H must go alone.

So, we sort the people in descending order of their weights.

Then, we use a two-pointer approach to ferry people across the river.

Solution in Python



class Solution:
    def numRescueBoats(self, people: List[int], limit: int) -> int:
        # descending order sort
        people = sorted(people, reverse = True)

        # stores the answer
        ans = 0

        # left and right pointer
        # left is extreme left
        # right is extreme right
        l,r = 0, len(people)-1

        # while the left pointer is before the right pointer
        while l < r:
            # if the weights of people
            # pointed to by the left and right pointer <= limit
            if people[l] + people[r] <= limit:
                # transport left person
                # move left pointer towards the right
                l += 1
                # transport right person
                # move right pointer towards the left
                r -= 1
                # increment num of boats by 1
                # as we send these 2 people in the same boat
                ans += 1
            # the weight of left and right person
            # exceeds the limit
            else:
                # ferry the left person alone
                l+=1
                # increase num of boats by 1
                ans += 1

        # if the left and right pointers point to the same person, 
        # then just one person is left to be transported
        # transport them alone
        if l == r:
            # increase number of boats by 1
            ans += 1

        return ans

Complexity

  • Time: $O(n \times log(n))$
    Since we sort the array.

  • Space: $O(1)$
    Since we only store a few integer pointers.

And we are done.