99% Running time | GREEDY | Easy to understand
Intuition\n Describe your first thoughts on how to solve this problem. \nTo maximize the total profit from assigning workers to jobs, it\'s essential to match e
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nTo maximize the total profit from assigning workers to jobs, it\'s essential to match each worker to the most profitable job they can perform based on their ability. By sorting both the workers and jobs, we can efficiently find the best job for each worker.\n\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nOrganize the Jobs: Create a dictionary to map each job difficulty to its highest profit. If multiple jobs have the same difficulty, keep the highest profit.\nSort Workers and Jobs: Sort the worker abilities and the job difficulties.\nGreedy Matching: For each worker, find the most profitable job they can perform by iterating through the sorted job difficulties. Use a two-pointer technique:\nOne pointer (i) iterates through workers.\nAnother pointer (j) iterates through job difficulties.\nAs long as the worker\'s ability is greater than or equal to the job\'s difficulty, update the current maximum profit.\nAssign this profit to the worker.\nSum the Profits: Add up all the profits assigned to each worker.\n# Complexity\n- Time complexity:O(nlogn+mlogm)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:O(n)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution(object):\n    def maxProfitAssignment(self, difficulty, profit, worker):\n        """\n        :type difficulty: List[int]\n        :type profit: List[int]\n        :type worker: List[int]\n        :rtype: int\n        """\n        # n jobs and m workers\n        n = len(difficulty) #  == len(profit)\n        difficultyDict = {}\n        totalProfit = 0\n\n        for i in range(n):\n            level = difficulty[i]\n            p = profit[i]\n            if level not in difficultyDict:\n                difficultyDict[level] = p\n            else:\n                if p > difficultyDict[level] :\n                    difficultyDict[level] = p\n        worker.sort()\n        i, j = 0, 0\n        m = len(worker)\n        currProfit = 0\n        difficulty = list(set(difficulty))\n        n = len(difficulty)\n        difficulty.sort()\n        maxProfit = 0\n        while i < m and j < n:\n            if worker[i] >= difficulty[j]:\n                maxProfit =  max(maxProfit, difficultyDict[difficulty[j]])\n                j += 1\n            else:\n                i += 1\n                totalProfit += maxProfit\n                currProfit = 0\n        while i < m:\n            totalProfit += maxProfit\n            i += 1\n\n\n        return totalProfit\n```\n\n![packied_spongebob.jpg](https://assets.leetcode.com/users/images/49ead31b-c0fc-4444-8c7c-e7152c83de88_1718674030.9513307.jpeg)\n
['Python']