Boats to Save People

Photo by Nathan Cima on Unsplash

You are given an array people where people[i] is the weight of the ith person, and an infinite number of boats where each boat can carry a maximum weight of limit. Each boat carries at most two people at the same time, provided the sum of the weight of those people is at most limit.

Return the minimum number of boats to carry every given person.

Example 1:

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

Example 2:

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

Example 3:

Input: people = [3,5,3,4], limit = 5
Output: 4
Explanation: 4 boats (3), (3), (4), (5)

Constraints:

• 1 <= people.length <= 5 * 104
• 1 <= people[i] <= limit <= 3 * 104

Explanation:

Lets take an example:
[7,9,3,2,8,6,4,5]
After Sorting
[2,3,4,5,6,7,8,9]

Lets try to solve using 2 pointer approach.

• One will be my left pointer intially on the extreme left i.e. starting of the array
• One will be my right pointer intially on the extreme right i.e. end of the array

Okay, now when I sum up the value of:
Left + Right pointer, there could be 2 Possiblities.

Possibility 1.0 (sum <= limit)      "sum could be less then or equals to my limit"
Possibility 2.0 (sum > limit)      "sum could be greater then my limit"

Let’s talk about what we’ll do when we face Possibility no. 1.0
If that's the case then we only require single boat & increment the boatCount, increment Left pointer & decrement the right pointer , as question has asked max 2 people allowed at a time and if their total weight is within limit both can be transferred and that’s why we have increment Left pointer & decrement the right pointer.

Let’s talk about what we’ll do when we face possibility no. 2.0
If that's the case then we only one person will go in boat & increment the boatCount & decrement the right pointer .

We have talk a lot, now let’s see it’s visually:

Code:

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

• Time Complexity :- O(NlogN)
• Space COmplexity :- O(1)