C++ Sorting Solution O(WLogW + DLogD) + DP Solution O(W+D)
Sorting Solution: O(WLogW + DLogD)\n\nRuntime: 172 ms, faster than 83.27% of C++ online submissions for Most Profit Assigning Work.\nMemory Usage: 38 MB, less t
**Sorting Solution: O(WLogW + DLogD)**\n\nRuntime: 172 ms, faster than 83.27% of C++ online submissions for Most Profit Assigning Work.\nMemory Usage: 38 MB, less than 47.43% of C++ online submissions for Most Profit Assigning Work.\n\n```\nclass Solution {\npublic:\n    int maxProfitAssignment(vector<int>& difficulty, vector<int>& profit, vector<int>& worker) {\n        \n        // Make difficult and profit pair vector jobs\n        vector<pair<int,int>>jobs;\n        \n        int d_size = difficulty.size();\n        for(int i=0;i<d_size;i++)\n            jobs.push_back(make_pair(difficulty[i],profit[i]));\n        \n        // sort jobs difficulty => O ( DLogD )\n        sort(jobs.begin(),jobs.end());\n        \n        // sort workers array difficulty => O ( WLogW ) \n        sort(worker.begin(),worker.end());\n        \n        int w_size = worker.size();\n        int maxProfit = 0;\n        int cprofit = 0;\n        int cjob = 0;\n        \n        // Loop through workers array to find profit for each worker => O ( W + D )\n        for(int i=0;i<w_size;i++)\n        {\n            // find max profit for worker[i] which is cprofit\n            // As jobs and workers are sorted, cprofit is always max for any difficulty range\n            while(cjob<d_size && jobs[cjob].first<=worker[i])\n            {\n                cprofit = max(cprofit,jobs[cjob].second);\n                cjob++;\n            }\n            \n            // update total max profit\n            maxProfit+= cprofit;\n        }\n        \n        return maxProfit;\n    }\n};\n```\n.\n.\n.\n**DP Solution: O( W + D )**\n\nRuntime: 140 ms, faster than 97.43% of C++ online submissions for Most Profit Assigning Work.\nMemory Usage: 35.7 MB, less than 97.24% of C++ online submissions for Most Profit Assigning Work.\n\n```\nclass Solution {\npublic:\n    int maxProfitAssignment(vector<int>& difficulty, vector<int>& profit, vector<int>& worker) {\n        \n        int dp[100001] = {};\n        int p_size = profit.size();\n        \n        for(int i=0;i<p_size;i++)\n            dp[difficulty[i]] = max(profit[i],dp[difficulty[i]]);\n        \n        for(int i=1;i<=100000;i++)\n            dp[i] = max(dp[i],dp[i-1]);\n        \n        int maxProfit = 0;\n        int w_size = worker.size();\n        \n        for(int i=0;i<w_size;i++)\n            maxProfit+=dp[worker[i]];\n        \n        return maxProfit;\n    }\n};\n```
['Dynamic Programming', 'C', 'Sorting']