Complete c++ solution with optimization
The first thing to do to solve this problem is to go through the problem statement and write in a notebook what\'s it\'s trying to say.\nThe constraints that co
The first thing to do to solve this problem is to go through the problem statement and write in a notebook what\'s it\'s trying to say.\nThe constraints that come up in my mind which we need to keep in mind while solving :\n1) Each boat can carry atmost two people and the sum of the weigths of them should be less or atmost the limit provided.\n2) We need to find the **minimum number of boats** that can save each one of them.\n**Approach 1:**\nThe first solution that comes up is obviously **brute force:**\nstep 1: check for pairs which can go in a boot together  without breaking the limit given\nand increment the count( count is for calculating  no. of boats)\nstep 2 :if there is no pair found and if a person is left out alone than that will go alone in  a seperate board. and increment the count.\n**Time complexity - O(N^2)**\n\n**Optimized Approach :** \nstep 1: **Sort the array**? \nbecause it will have us to find people with heavier weigths. \n**To minimize the number of boats we can pairup and send one lighter in weight and one heavier in weight together (only if they doesn\'t cross the given limit)**\nstep 2:\nUse **Two pointer approach** and keep a count variable which will be storing the minimum number of boats required to rescue all of them. \nput a left pointer at the index 0 and a right pointer at  the end of the people array \n calculate sum which will be equal to people[i] + people[j]\n \n *Here two cases arrises:*\n Case 1: \n if the sum is smaller than or equivalent to the given limit of weight than they can go in a boat together so increase the count of boat and make the left pointer(left++) and right pointer(right--) move.\n case 2:\n if the sum is greater than limit than there is can be minimum number of boats if we can make the heavier boat go alone and the lighter weight go in the next turn.\n hence increment the boat count and only move right pointer(decrement).\n\n**Time complexity - O(N Log N)**\n```\nclass Solution {\npublic:\n    int numRescueBoats(vector<int>& people, int limit) {\n        // sort the array \n        sort(people.begin(), people.end());\n        int count = 0; // to store the minimum number boats required to save people \n        int left = 0;\n        int right = people.size() -1;\n        while(left <= right){\n           int sum = people[left] + people[right];\n            \n            //two cases arises:\n            if(sum <= limit){\n              // when sum is less or atmost equivalent to given limit;\n                count++;\n                left++;\n                right--;\n            \n            }\n            if(sum > limit){\n                // if the sum comes greater than limit than push the heavier weight person to go alone in the boat.\n              count++;\n                right--;\n            }\n        }\n        return count;\n    }\n};\n```\n**please upvote if you like the solution**\n*Comment if have suggestions or doubts*\n
['Two Pointers', 'C', 'C++']