[Python] two pointers solution, explained
The key intuition here is that:\n1. Every person must be saved.\n2. For each person it is better to find another person with biggest weight, such that sum of th
The key intuition here is that:\n1. Every person must be saved.\n2. For each person it is better to find another person with **biggest** weight, such that sum of their weights is no more than limit. Indeed, if we put another person, we will have subproblem A, which is always worse than if we put biggest one (subproblem B): every solution of B can be also used to solve A as well, but not the opposite. \n\nSo, let us sort our people by weight and use two pointers technique to allocate them to boats:\n1. If `people[beg] + people[end] <= limit`, then we can put these two persons in one boat, so we move `beg` to the right, `end` to the left and increment `ans` by one.\n2. In opposite case it means, that person with smallest weight and with biggest weight so far can not be put in one boat, so, we need to decrease weight: movint `end` pointer one step to the left.\n\n**Complexity**: time complexity is `O(n log n)`, because we sorted our data and then we have `O(n)` for two-pointers approach. Space complexity is `O(n)`.\n\n```\nclass Solution:\n    def numRescueBoats(self, people, limit):\n        people.sort()\n        beg, end, ans = 0, len(people) - 1, 0\n        while beg <= end:\n            if people[beg] + people[end] <= limit:\n                beg += 1\n            ans += 1\n            end -= 1\n                \n        return ans\n```\n\nIf you have any questions, feel free to ask. If you like solution and explanations, please **Upvote!**
['Two Pointers', 'Greedy']