🧠 Intuition, 📚 Approach, and 📈 Complexity
\uD83D\uDE4F\uD83D\uDE4F\uD83D\uDE4FPLEASE UPVOTE IF YOU FIND THIS HELPFUL , PLEASE \uD83D\uDE4F\uD83D\uDE4F\uD83D\uDE4F\uD83D\uDE4F \n# Intuition\n Describe yo
# \uD83D\uDE4F\uD83D\uDE4F\uD83D\uDE4FPLEASE UPVOTE IF YOU FIND THIS HELPFUL , PLEASE \uD83D\uDE4F\uD83D\uDE4F\uD83D\uDE4F\uD83D\uDE4F \n# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe key observation is that for a given difficulty level, the maximum profit can be carried forward to the next higher difficulty. This allows for efficient querying of the maximum profit for any worker\'s ability.\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. Store Difficulty-Profit Pairs in a Multimap:\n2. Insert the difficulty-profit pairs into a multimap to maintain the order of difficulties. Build a Maximum Profit Map:\n3. Traverse the multimap and maintain a running maximum profit (currMax).Use a map to store the maximum profit up to each difficulty level.Query Maximum Profit for Each Worker\n4. For each worker\'s ability, use the lower_bound function to find the first difficulty that is not less than the worker\'s ability.\nIf the worker\'s ability exactly matches a difficulty, use the corresponding profit.\n5. If not, check the previous difficulty\'s profit (if exists) to find the maximum profit the worker can earn.\nCache the results to avoid redundant calculations for the same worker ability.\nReturn Total Maximum Profit:\n\nSum the maximum profits for all workers and return the total.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nInserting n elements into the multimap and map takes O(nlogn).\nQuerying the map for each of the m workers\' abilities takes O(mlogn).\nOverall, the time complexity is O((n+m)logn).\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nThe multimap and map each require O(n) space.\nThe unordered_map for caching results takes O(m) space.\nOverall, the space complexity is O(n+m).\n\n# Code\n```\nclass Solution {\npublic:\n    int maxProfitAssignment(vector<int>& d, vector<int>& p, vector<int>& w) {\n        multimap<int, int> mp;\n        for (int i = 0; i < p.size(); i++) {\n            mp.insert({d[i], p[i]});\n        }\n\n        // Use a map to store the maximum profit up to each difficulty\n        map<int, int> maxProfits;\n        int currMax = 0;\n        for (const auto& it : mp) {\n            currMax = max(currMax, it.second);\n            maxProfits[it.first] = currMax;\n        }\n\n        int maxP = 0;\n        unordered_map<int, int> wdone;\n        for (int i : w) {\n            if (wdone.find(i) != wdone.end()) {\n                maxP += wdone[i];\n                continue;\n            }\n            int maxi = 0;\n\n            auto it = maxProfits.lower_bound(i);\n            if (it != maxProfits.end()) {\n                if (it->first == i) {\n                    maxi = max(maxi, it->second);\n                } else {\n                    if (it == maxProfits.begin()) continue;\n                    --it;\n                    maxi = max(maxi, it->second);\n                }\n            } \n            else {\n                if (!maxProfits.empty()) {\n                     maxi = max(maxi, maxProfits.rbegin()->second);\n                }\n            }\n            maxP += maxi;\n            wdone[i] = maxi;\n        }\n        return maxP;\n    }\n};\n```\n\uD83D\uDE4F\uD83D\uDE4F\uD83D\uDE4FPLEASE UPVOTE IF YOU FIND THIS HELPFUL , PLEASE \uD83D\uDE4F\uD83D\uDE4F\uD83D\uDE4F\uD83D\uDE4F
['Dynamic Programming', 'Ordered Map', 'C++']