C++ ||  java || python|| 2 Pointer || Easy || Simple & Short ||
Intuition\n Describe your first thoughts on how to solve this problem. \nThe intuition behind the solution lies in optimizing the number of boats needed to resc
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe intuition behind the solution lies in optimizing the number of boats needed to rescue all the people, given the weight limit per boat.\n\nSorting: Sorting the array of people\'s weights allows us to pair the heaviest and lightest individuals efficiently. It ensures that if two people are to be placed in a boat, they are the closest in weight to each other, minimizing the chances of exceeding the weight limit.\nTwo-pointer approach: Using two pointers allows us to consider pairs of people from both ends of the sorted array. By starting with the lightest and heaviest individuals, we can determine if they can be placed together in a boat without exceeding the weight limit.\nIterative checking: While iterating through the array with two pointers, we check if the sum of weights of the current pair of people is within the weight limit of the boat. If it is, we move the lighter person\'s pointer to the right, indicating they are accounted for. Regardless, we move the heavier person\'s pointer to the left, as they are already paired or alone in a boat.\nCounting boats: Incrementing the count at each iteration signifies that a boat is being used. The count will eventually represent the minimum number of boats needed to rescue all people.\nIn summary, the intuition is to pair people optimally, starting with the lightest and heaviest individuals, and incrementally move towards the middle of the sorted array, minimizing the number of boats required to rescue everyone.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nThe approach used in the numRescueBoats function is to sort the array of people\'s weights in ascending order. Then, it uses a two-pointer technique where one pointer (i) starts from the beginning of the array and the other pointer (j) starts from the end of the array.\n\nThe function then iterates over the array while the two pointers (i and j) don\'t cross each other. At each iteration, it checks if the sum of the weights of the person at pointer i and the person at pointer j is less than or equal to the limit. If it is, it means both of these people can fit into one boat, so it increments i to move to the next person. Regardless of whether a pair of people fits into a boat or not, it decrements j to consider the next person from the heavier end.\n\nFinally, it increments the count variable at each iteration, indicating the number of boats needed.\n\nThis approach ensures that the heaviest person is paired with the lightest person who can fit into the same boat, thus minimizing the number of boats required to rescue all the people.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n O(n log n).\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n O(1.\n# Code\n\n\n# C+++\n\n```\nclass Solution {\npublic:\n    int numRescueBoats(vector<int>& people, int limit) {\n        sort(people.begin(),people.end());\n        int i = 0, j = people.size()-1, count = 0;\n        while(i<=j){\n            if(people[i] + people[j] <= limit)i++;\n            count++;\n            j--;\n        }\n        return count;\n    }\n};\n```\n\n\n\n# JAVA\n\n```\nimport java.util.Arrays;\n\nclass Solution {\n    public int numRescueBoats(int[] people, int limit) {\n        Arrays.sort(people);\n        int i = 0, j = people.length - 1, count = 0;\n        while (i <= j) {\n            if (people[i] + people[j] <= limit) i++;\n            count++;\n            j--;\n        }\n        return count;\n    }\n}\n\n```\n\n\n# Python\n\n```\nclass Solution:\n    def numRescueBoats(self, people: List[int], limit: int) -> int:\n        people.sort()\n        i, j, count = 0, len(people) - 1, 0\n        while i <= j:\n            if people[i] + people[j] <= limit:\n                i += 1\n            count += 1\n            j -= 1\n        return count\n\n```
['Array', 'Two Pointers', 'Greedy', 'Sorting', 'Python', 'C++', 'Java']