✅ 881. Boats to Save People || C++ || 2 Pointers || Greedy Algorithms || Approach explanation

Intuition & Approach
In this problem, they gave us two parametes which are vectory array 'the weights of persons' and an integer which is the maximum weight that boat can carry. And what we need to return is the minimum number of boats to carry every given person.

So, In navie thinking, we could check all the persons in people array whether they can share their boat with anoterh person or not. However, it will take times when we decide the person who share the boat... we need to find one person in the array ("Each boat carries at most two people at the same time"). Therefore, we need to find person who can pair with the person we select, we can reduce our time complexity in here!

Let's think better way to solve this problem. There were three things we need to care about here.

1. We need to sweep at least one time to decide two persons who share their boat.
   => 'It will take O(n) and it isn't possible to pass this,,'
2. We can reduce our time when find a person who can pair with the person when we decided when we sweep.
   => 'If we sort the array, and use two pointers, we can get more optimization way..!'
3. Each boat carries at most two people at the same time.
   => 'It doesn't mean that we use another while loop to put persons a boat as much as possible because it will only take two persons,, And this greedy logic could work'

 

Algorithm

1. Sort the array
2. Declare two pointers which are pointing the first idx(the lightest person) and the last idx(the heavist person)
3. Using Two pointers logic, we can find whether the person can pair with anyone or not

 

Code

class Solution {
public:
    int numRescueBoats(vector<int>& people, int limit) {
        sort(people.begin(), people.end());
        int pleft=0, pright=people.size()-1;
        int nBoat=0;
        
        while(pleft<=pright){
            nBoat++;
            // "Each boat carries at most two people at the same time"
            if(people[pleft]+people[pright] <=limit){
                pleft++;
            }
            pright--;            
        }
        
        return nBoat;
    }
};

 

Comlexity Analysis

• Time Complexity : O(NlogN), where N is the length of people array.
• Sapce Complexity : O(NlogN)
  • Actually, it depends on which sort algorithms you use,,, some sort alogorithms such as merge sort will haveO(N) space complexity to sort people array in place. However, it is implemented sort() function in C++ by using a hybrid of Quick Sort, Heap Sort, and Insertion Sort, with worst-case space complexity of O(NlogN)