🚀 2 Approaches: Monotonic Stack || Sort Only || 10 lines || Concise code
Intuition\n Describe your first thoughts on how to solve this problem. \nFirst, we know that the more skilfull worker is, the more difficult work he can handle,
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nFirst, we know that the more skilfull worker is, the more difficult work he can handle, so sorting is needed to keep track the best work (good profit and less cost). \nThis problem is confusing because sometimes, there are **some works that is so difficult but small profit**. We need to get rid of them. \n\n# Approach 1: Monotonic Stack\n-> Using monotoric stack to remove all of that redundant works.\n\n**Note**: This is more straightforward solution with me to think about it in the interview. **But if you think it is long, just move on to the next approach.**\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity: O(m*log(m) + n*(log(n)))\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(m)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```Python\nclass Solution:\n    def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:\n        # Step 1: Prepare all data\n        if max(worker) < min(difficulty): return 0\n        worker.sort()\n        profit_diff = sorted(list(zip(profit, difficulty)))\n        optimal_profits = [] # monotoric queue\n        # Step 2: Get the OPTIMAL works only\n        for i in range(len(profit_diff) -1, -1, -1):\n            if i == len(profit_diff) -1:\n                optimal_profits.append(profit_diff[i])\n            else:\n                if profit_diff[i][1] < optimal_profits[-1][1]:\n                    optimal_profits.append(profit_diff[i])\n        optimal_profits = [(0,0)] + optimal_profits[::-1] # dummy node (0,0)\n        # Step 3: Get total profit\n        profit_i, total_profit = 0, 0\n        for level in worker:\n            while profit_i+1 < len(optimal_profits) and optimal_profits[profit_i+1][1] <= level:\n                profit_i += 1\n            total_profit += optimal_profits[profit_i][0]\n        return total_profit\n\n```\n\n# Approach 2: Sorting Only\nThis is a shorter solution, so we don\'t need monotonic stack here.\nWe use difficulty as parameter to sort. On the way of traversing difficulty, we keep track of the max profit worker can get: `cur_best_profit`\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity: O(m*log(m) + n*(log(n)))\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(m)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```Python\nclass Solution:\n    def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:\n        # Step 1: Prepare all data\n        worker.sort()\n        diff_profit = [(0,0)] + sorted(list(zip(difficulty, profit))) # dummy node: (0,0)\n        # Step 2: Get total profit\n        diff_i, cur_best_profit = 0, 0\n        total_profit = 0\n        for level in worker:\n            while diff_i+1 < len(diff_profit) and diff_profit[diff_i+1][0] <= level:\n                cur_best_profit = max(cur_best_profit, diff_profit[diff_i+1][1])\n                diff_i += 1\n            total_profit += cur_best_profit\n        return total_profit\n\n```\n\n**I hope it help you guys. Thank you**\n![upvote.png](https://assets.leetcode.com/users/images/0202839b-6346-499e-ab4d-3d6221cb1b68_1718678531.8385522.png)\n\n\n
['Sorting', 'Monotonic Stack', 'Python3']