Greedy+Sort/Counting Sort then 2-pointer||7ms beats 100%
Intuition\n Describe your first thoughts on how to solve this problem. \n3 methods Greedy. At best 1 light+1 heavy can be in a boat. \n1 is using sorting, then 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n3 methods Greedy. At best 1 light+1 heavy can be in a boat. \n1 is using sorting, then 2-pointer\n2nd using counting sort to replace std::sort\nLater consider furthermore optimization.\n3rd C++ outperforms other method with the elapsed time 7ms.\n# Approach\n<!-- Describe your approach to solving the problem. -->\n[Please turn on English subtitles if necessary]\n[https://youtu.be/--IlX3x54nk?si=3V08KKTGnfk2ANId](https://youtu.be/--IlX3x54nk?si=3V08KKTGnfk2ANId)\n1. Since every one is <= limit. Each boat can transport at least 1, but at most 2.\n2. After sorting, use 2-pointer, in form of a loop with control variable r=people.size()-1...with the condition l<=r, for the Greedy process needs to check \n```\npeople[l]+people[r]<=limit\n```\nif yes, the people[l] can go with people[r], so l++; otherwise this boat can carry only people[r].\n\nLet\'s consider the testcase=`[1,2,3,4,5,8,9] 9`.\nThe Greedy process with 2-pointer is as follows:\n```\nboat 1:9,\nboat 2:8,1\nboat 3:5,2\nboat 4:4,3\n```\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n1. sort+2-pointer: $O(n\\log n)$\n2. Counting sort+2-pointer $O(n+m)$\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n$O(sort)$\n# Code||18ms beats 100%\n```\n#pragma GCC optimize("O3", "unroll-loops")\nclass Solution {\npublic:\n    int numRescueBoats(vector<int>& people, int limit) {\n        unsigned freq[30001]={0};\n        int maxW=0, minW=30001;\n        for(int x: people){\n            freq[x]++;\n            maxW=max(maxW, x);\n            minW=min(minW, x);\n        }\n        for (int i=minW, j=0; i<=maxW; i++){\n            int f=freq[i];\n            fill(people.begin()+j, people.begin()+j+f, i);\n            j+=f;\n        }      \n        int x=0;\n        for(int l=0, r=people.size()-1;l<=r; r--){\n            x++;\n            if (people[l]+people[r]<=limit)\n                l++;          \n        }\n        return x;\n    }\n};\n\n\nauto init = []() {\n    ios::sync_with_stdio(0);\n    cin.tie(0);\n    cout.tie(0);\n    return \'c\';\n}();\n```\n# C++ using sort||41ms Beats 97.66%\n```\n#pragma GCC optimize("O3", "unroll-loops")\nclass Solution {\npublic:\n    int numRescueBoats(vector<int>& people, int limit) {\n        sort(people.begin(), people.end());       \n        int x=0;\n        for(int l=0, r=people.size()-1;l<=r; r--){\n            x++;\n            if (people[l]<=limit-people[r])\n                l++;          \n        }\n        return x;\n    }\n};\n```\n# Python code\n```\nclass Solution:\n    def numRescueBoats(self, p: List[int], limit: int) -> int:\n        p.sort()\n        x=0\n        l, r=0, len(p)-1\n        while l<=r:\n            x+=1\n            if p[l]+p[r]<=limit:\n                l+=1\n            r-=1\n        return x\n        \n```\n# 3rd using freq||C++ 7ms beats 100%, C beats 100%\nJust use freq array, not proceed the whole counting sort which is very fast.\n```C++ []\nclass Solution {\npublic:\n    int numRescueBoats(vector<int>& people, int limit) {\n        unsigned freq[30001]={0};\n        int maxW=0, minW=30001;\n        for(int x: people){\n            freq[x]++;\n            maxW=max(maxW, x);\n            minW=min(minW, x);\n        }\n\n        int x=0, f1, l, r;\n        for(l=minW, r=maxW; l<r; ){\n            while(l<r && freq[r]==0) r--;\n            int f0=freq[r];\n            while(l<r && freq[l]==0) l++;\n            f1=freq[l];\n        //    cout<<r<<", freq[r]="<<freq[r]<<", l="<<l<<", freq[l]="<<freq[l]<<endl;\n            if (r==l) break;\n            int boat=min(f0, f1);\n            x+=boat;\n            freq[r]-=boat;\n            if(l+r<=limit){\n                freq[l]-=boat;\n                if (f1<=f0) l++;\n            } \n        }\n    //    cout<<r<<","<<freq[r]<<endl;\n        x+=(r*2>limit)?freq[r]:(freq[r]+1)/2;\n        return x;\n    }\n};\n\n\n\nauto init = []() {\n    ios::sync_with_stdio(0);\n    cin.tie(0);\n    cout.tie(0);\n    return \'c\';\n}();\n```\n```C []\n#pragma GCC optimize("O3", "unroll-loops")\nint numRescueBoats(int* people, int peopleSize, int limit) {\n    unsigned freq[30001]={0};\n    int maxW=0, minW=30001;\n    for(register int i=0; i<peopleSize; i++){\n        unsigned x=people[i];\n        freq[x]++;\n        if (x>maxW) maxW=x;\n        if (x<minW) minW=x;\n    }\n    unsigned x=0, f1, l, r;\n    for(l=minW, r=maxW; l<r; ){\n        while(l<r && freq[r]==0) r--;\n        int f0=freq[r];\n\n        while(l<r && freq[l]==0) l++;\n        f1=freq[l];\n            \n        if (r==l) break;\n        int boat=f0<f1?f0:f1;\n        x+=boat;\n        freq[r]-=boat;\n        if(l+r<=limit){\n            freq[l]-=boat;\n            if (f1<=f0) l++;\n        } \n    }\n    x+=(r*2>limit)?freq[r]:(freq[r]+1)/2;\n    return x;\n}\n```
['Two Pointers', 'Greedy', 'C', 'Sorting', 'Counting Sort', 'C++', 'Python3']