Greedy+ sorting||23ms Beats 99.74%
Intuition\n Describe your first thoughts on how to solve this problem. \nIt\'s greedy problem. Just sorting can solve it.\n\nOther approach may be tried later. 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nIt\'s greedy problem. Just sorting can solve it.\n\nOther approach may be tried later. \n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. Construct the container `d_p` holding info pair `(difficulty[i], profit[i])`\n2. Sort `d_p`\n3. Sort `worker`\n4. Use a loop to  assign the bestProfit job for `worker[i]` for each i\n5. `maxProfit`=sum of such bestProfit.\n6. 2nd provided C++ is also a Greedy method; sorting `d_p`, then reuse `d_p` to hold the info pair `(difficulty[i], best_profit[i])`. Finally use binary search (`upper_bound`) to compute `maxProfit`\n7. 3rd C++ is a variant for the 1st approach using radix sort with 64 buckets.\n# Why the nested loop has time complexity O(n+m)?\nThe main idea is greedy, but there are different ways to implement.\nIn the 2nd part of 1st code is using\n```\nint idx = 0;\n\nfor (int i = 0; i < m; i++) {\n    while (idx < n && worker[i] >= d_p[idx].first) {\n        bestProfit = ...\n        idx++;\n        // uncomment the following line to see 2 pointers\n        // cout<<i<<", "<< idx<<endl;\n    }\n    maxProfit+= ...\n}\n```\n2 pointers `i & idx` go from 0 to m-1 (n-1 respectively) & never go backward; each iteration will move either i or idx by 1, therefor it is `O(n+m)` of TC.\n\nIf you\'re still skeptish, you can uncomment the comment for outputs.\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n$$O(n\\log n+ m\\log m)$$\nSame as LC said\n![826cp.png](https://assets.leetcode.com/users/images/392b5678-11f2-4e8b-973f-2a775a13b793_1718671827.4159148.png)\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n$$O(n)$$\n# Code||C++ 23ms Beats 99.74%\n```\nclass Solution {\npublic:\n    using int2=pair<int, int>; // (difficulty[i], profit[i])\n    int maxProfitAssignment(vector<int>& difficulty, vector<int>& profit, vector<int>& worker) {\n        const int n=profit.size(), m=worker.size();\n        vector<int2> d_p(n);\n        for(int i=0; i<n; i++) \n            d_p[i]={difficulty[i], profit[i]};\n\n        sort(d_p.begin(), d_p.end());\n        sort(worker.begin(), worker.end());\n        \n        int maxProfit=0,  idx=0, bestProfit = 0;\n\n        for (int i = 0; i < m; i++) {\n            // Increase index to the next worker\'s ability\n            while (idx < n && worker[i] >= d_p[idx].first) {\n                bestProfit = max(bestProfit, d_p[idx].second);\n                idx++;\n            }\n            maxProfit+= bestProfit;\n        }\n        return maxProfit;\n    }\n};\n\n\n\n\nauto init = []() {\n    ios::sync_with_stdio(false);\n    cin.tie(nullptr);\n    cout.tie(nullptr);\n    return \'c\';\n}();\n\n```\n# C++ sort info pair (difficulty[i], profit[i]) + using upper_bound||30ms Beats 99.10%\n\nThis method is slight slower than the 1st one. The time complexity is $O((n+m)\\log n)$\n\n```\nclass Solution {\npublic:\n    using int2=pair<int, int>; // (difficulty[i], profit[i])\n    int maxProfitAssignment(vector<int>& difficulty, vector<int>& profit, vector<int>& worker) {\n        const int n=profit.size(), m=worker.size();\n        vector<int2> d_p(n);\n        for(int i=0; i<n; i++) \n            d_p[i]={difficulty[i], profit[i]};\n\n        sort(d_p.begin(), d_p.end());\n        for(int i=1; i<n; i++)//(difficulty[i], bestprofit)\n            d_p[i].second = max(d_p[i].second, d_p[i-1].second);\n\n        int maxProfit=0;\n        for(int able: worker){\n            int i=upper_bound(d_p.begin(), d_p.end(), make_pair(able, INT_MAX))-d_p.begin();\n                maxProfit+=(i>0)?d_p[i-1].second:0;\n        }    \n       \n        return maxProfit;\n    }\n};\n\n\n\n\nauto init = []() {\n    ios::sync_with_stdio(false);\n    cin.tie(nullptr);\n    cout.tie(nullptr);\n    return \'c\';\n}();\n```\n# Variant of 1st approach using radix sort||23ms Beats 99.74%\n\ninstead of `std::sort`, radix_sort is implemented. TC= $O(n+m)$.\n```\nclass Solution {\npublic:\n    using int2 = pair<int, int>; // (difficulty[i], profit[i])\n    \n    inline static void radix_sort(vector<int2> & pair) {\n        vector<int2> bucket[64];\n        // 1st round\n        for (auto& [x, i] : pair)\n            bucket[x & 63].emplace_back(x, i);\n        int index = 0;\n        for (auto& B : bucket) {\n            for (auto& v : B)\n                pair[index++] = v;\n            B.clear();\n        }\n        // 2nd round\n        for (auto& [x, i] : pair)\n            bucket[(x >> 6) & 63].emplace_back(x, i);\n        index = 0;\n        for (auto& B : bucket) {\n            for (auto& v : B)\n                pair[index++] = v;\n            B.clear();\n        }\n        // 3rd round\n        for (auto& [x, i] : pair)\n            bucket[(x >> 12)].emplace_back(x, i);\n        index = 0;\n        for (auto& B : bucket) {\n            for (auto& v : B)\n                pair[index++] = v;\n            B.clear();\n        }\n    }\n\n    inline static void radix_sort(vector<int> & nums) {\n        vector<int> bucket[64];\n        // 1st round\n        for (auto x : nums)\n            bucket[x & 63].emplace_back(x);\n        int index = 0;\n        for (auto& B : bucket) {\n            for (auto v : B)\n                nums[index++] = v;\n            B.clear();\n        }\n        // 2nd round\n        for (auto x : nums)\n            bucket[(x >> 6) & 63].emplace_back(x);\n        index = 0;\n        for (auto& B : bucket) {\n            for (auto v : B)\n                nums[index++] = v;\n            B.clear();\n        }\n        // 3rd round\n        for (auto x : nums)\n            bucket[x >> 12].emplace_back(x);\n        index = 0;\n        for (auto& B : bucket) {\n            for (auto v : B)\n                nums[index++] = v;\n            B.clear();\n        }\n    }\n\n    static int maxProfitAssignment(vector<int> & difficulty, vector<int> & profit,\n                            vector<int> & worker) {\n        const int n = profit.size(), m = worker.size();\n        vector<int2> d_p(n);\n        for (int i = 0; i < n; i++)\n            d_p[i] = {difficulty[i], profit[i]};\n\n        radix_sort(d_p);\n        radix_sort(worker);\n\n        int maxProfit = 0, idx = 0, bestProfit = 0;\n\n        for (int i = 0; i < m; i++) {\n            // Increase index to the next worker\'s ability\n            while (idx < n && worker[i] >= d_p[idx].first) {\n                bestProfit = max(bestProfit, d_p[idx].second);\n                idx++;\n            }\n            maxProfit += bestProfit;\n        }\n        return maxProfit;\n    }\n};\n\nauto init = []() {\n    ios::sync_with_stdio(false);\n    cin.tie(nullptr);\n    cout.tie(nullptr);\n    return \'c\';\n}();\n```
['Two Pointers', 'Binary Search', 'Greedy', 'Sorting', 'Radix Sort', 'C++']