[Java/Python 3] O(nlogn) code, sorting + greedy, w/ greedy algorithm proof.
\nPush from two ends of the sorted array people.\n1. if the 2 ends, people[lo] and people[hi], can fit in a boat, move the 2 ends;\n2. otherwise move only the h
\nPush from two ends of the sorted array ***people***.\n1. if the 2 ends, ```people[lo]``` and ```people[hi]```, can fit in a boat, move the 2 ends;\n2. otherwise move only the high end, and the low end stays.\nIn other words: **always move the high end, but the low end depends on if we can cram it into a boat with the high end.**\n3. repeat the above till the 2 ends meet.\n\n```java\n    public int numRescueBoats(int[] people, int limit) {\n        Arrays.sort(people);\n        int ans = 0; \n        for (int hi = people.length - 1, lo = 0; hi >= lo; --hi, ++ans) { // high end always moves\n            if (people[lo] + people[hi] <= limit) { // low end moves only if it can fit in a boat with high end.\n                ++lo; \n            }\n        }\n        return ans;\n    }\n```\n```python\n    def numRescueBoats(self, people: List[int], limit: int) -> int:\n        boat, lo, hi = 0, 0, len(people) - 1\n        people = sorted(people)\n        while lo <= hi:\n            if people[hi] + people[lo] <= limit:\n                lo += 1\n            boat += 1\n            hi -= 1\n        return boat\n```\n\n**Update:**\nSince some people challenge or have questions about the greedy algorithm, I provide the proof as follows.\n\n**Proof of the correctness of the greedy algorithm:**\nDenote ```S``` as one of the optimal solutions, and ```O``` as our algorithm output solution.\n**1. Greedy choice property.**\n\nStarting from the **heaviest person hi**, there are 2 possible cases: \na) if ```hi``` can NOT fit in a boat with any other, then both in ```S``` and ```O```, ```hi``` is in a boat **alone**. Apparently, our first step is optimal and the greedy choice property holds;\nb) if ```hi``` CAN fit in a boat with at least 1 other person, then \nin ```O```, ```hi``` and **lightest person lo** together must be in same boat, according to our algorithm. \n\nIn ```S```, if they are also in same boat, then our first step is optimal and the greedy choice property holds; \nIf ```hi``` and ```lo``` are not in same boat, say in ```boat-hi``` and ```boat-lo``` respectively, then we can swap ```hi``` with ```lo```\'s boat mate, say index ```m```. Obviously, ```people[m] <= people[hi]```, therefore the swap is feasible. Since the swap results no extra boat(s), a new optimal solution ```T``` is obtained. That indicates our first step--put ```hi``` and ```lo``` into same boat--is an optimal step and  and greedy choice property also holds.\n\n**2.optimal substructure property.**\n\nLet ```P``` be the original problem at scale ```n```, where ```n = people.length```. From the above 1, after first step, we have a subproblem ```P\'``` at scale ```n\' ```(```n\' = n - 1 or n - 2```, depends on ```hi``` in a boat alone or not). Similary, we have ```hi\'``` and ```lo\'``` and can do next step as in 1. \n\nSince in 1 we proved ```T``` is an optimal solution, and the solution of ```P\'```, say ```O\'```, contained within ```T``` is also an optimal one. Thus the the problem has the optimal substructure property.\n\nCombine 1 and 2, we complete the proof.\n\n**end of proof.**\n\n----\n\nSimilar Problem:\n\n[2178. Maximum Split of Positive Even Integers](https://leetcode.com/problems/maximum-split-of-positive-even-integers/discuss/1783317/JavaPython-3-Greedy-w-brief-explanation-and-analysis./)
['Two Pointers', 'Greedy', 'Java', 'Python3']