O(n) and O(nlogn) solutions in Python for beginners 🤗
DP Solution\nI\'m quite surprised there aren\'t many linear solutions for this problem in the Solutions tab, so I decided to add one! I hope my code is straight
# DP Solution\nI\'m quite surprised there aren\'t many linear solutions for this problem in the Solutions tab, so I decided to add one! I hope my code is straightforward. The idea is to create a dynamic programming (DP) array that stores the maximum possible profit for each level of difficulty. This allows us to efficiently track the best profit we can achieve for any given difficulty level.\n\n## Complexity\n- Time complexity: $$O(n)$$\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:\n    def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:\n        \n        dp = [0 for _ in range(100001)]\n        hashmap = defaultdict(int) # difficulty: max_profit\n        for idx in range(len(difficulty)):\n            hashmap[difficulty[idx]] = max(hashmap[difficulty[idx]], profit[idx])\n        for idx in range(1, len(dp)):\n            dp[idx] = max(dp[idx - 1], hashmap[idx])\n        res = 0\n        for wrk in worker:\n            res += dp[wrk]\n        return res\n```\n\n# Sorting Solution\nThis solution is quite straightforward. Similar approaches can be found in the Solutions section. We sort everything first and then iterate through both arrays, keeping track of the best profit at each step.\n\n## Complexity\n- Time complexity: $$O(nlogn)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(1)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n\n```\nclass Solution:\n    def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:\n\n        jobs = sorted(zip(difficulty, profit))\n        res, i, best = 0, 0, 0\n        for ability in sorted(worker):\n            while i < len(jobs) and ability >= jobs[i][0]:\n                best = max(best, jobs[i][1])\n                i += 1\n            res += best\n        return res\n```
['Python3']