Simple sort and two pointer with detailed provement
Sort people, then for each minimum people[l], find the greatest available people[r] so that l, r can use the same boat until l, r meets.\n\nNow let\'s prove it.
Sort people, then for each minimum `people[l]`, find the greatest available `people[r]` so that `l, r` can use the same boat until `l, r` meets.\n\nNow let\'s prove it.\n\nLet `f(people)` be the least boats we need.\n\nFor `f(people[l:r])` (inclusive), let\'s prove following two statements:\n\n* If `people[l]+people[r]>limit`, `f(people[l:r])=f(people[l:r-1])+1` (it\'s safe to put `r` into a boat alone)\n\t* This is obviously true because nobody can share a boat with `r`, even the lightest guy `l`\n* If `people[l]+people[r]<=limit`, `f(people[l:r])=f(people[l+1:r-1])+1` (it\'s safe to put `l, r` in a same boat)\n\t* Here we pair `l, r`, use one boat, remaining question is `f(people[l+1:r-1])`\n\t* Think of all other cases of `l`:\n\t\t* if `l` is put in a single boat, use one boat, remaining question is `f(people[l+1:r])`, having one more people can\'t give better solution.\n\t\t* if `l` is put in a boat with some `l<m<r`, remaining question is `f(people[l+1:m-1]+people[m+1:r])`, compare this question with `f(people[l+1:r-1])=f(people[l+1:m-1]+people[m:r-1])`, we can see, the heaviest (r-m) people in pair with `r` solution always have lower or equal weight compare with pair with `m` situation, so for the optimal solution for `f(people[l+1:m-1]+people[m+1:r])`, replace the [m+1:r] with [m:r-1] always give a same count of boats. So pair with `r` can\'t be worse than pair with some `m`.\n\n\nGet the above two statements proved, we can use two pointers to solve this problem.\n\n```\nclass Solution:\n\n    def numRescueBoats(self, people, limit):\n        N = len(people)\n        people.sort()\n        \n        l, r = 0, N-1\n        \n        cnt = 0\n        \n        while l<=r:\n            if people[l]+people[r]<=limit:\n                l += 1\n                r -= 1\n            else:\n                r -= 1\n            cnt += 1\n            \n        return cnt\n```
[]