Beats 96.16%✅| Python 💻 | EASY, CLEAR Explanation📙
Beats 96.16%\u2705| Python \uD83D\uDCBB | EASY, CLEAR Explanation\uD83D\uDCD9\n\n## 1. Proof (Python3)\n Describe your first thoughts on how to solve this probl
# Beats 96.16%\u2705| Python \uD83D\uDCBB | EASY, CLEAR Explanation\uD83D\uDCD9\n\n## 1. Proof (Python3)\n<!-- Describe your first thoughts on how to solve this problem. -->\n![image.png](https://assets.leetcode.com/users/images/a5154a52-af89-4657-a687-c9aa04201e99_1718804281.7354114.png)\n\n\n## 2. Algorithms\n* Sorting\n* One pointer\n* Greedy\n\n## 3. Code (with inline explanation)\n```python3 []\nclass Solution:\n    def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:\n        \'\'\'\n        1. Prepare our "greedy" materials\n        \'\'\'\n        pro_diff = sorted(zip(profit, difficulty), reverse=True) # Sort the profit by descending order (each tuple contains each profit[i] links with its corresponding difficulty[i])\n        worker.sort() # Ascending order\n        cur_wk = len(worker) - 1 # Pointer starts from the last index of `worker` - the worker with highest ability (because we sorted)\n        res = 0 # Result\n        \'\'\'\n        2. Greedy\n            - Going from the job with most profit and sequentially to least profit (sorted)\n            - At each job, count the number of valid workers with each worker satisfies the condition worker\'s ability > job\'s difficulty\n            - We calculate the profit that those valid workers can generate by doing this job = number of valid workers for this job * this job\'s profit\n            - As we go from the highest-profit job and count all the eligible workers, we get the max profit for this job, the same logic applies with lower-profit jobs\n            => We get the max profit of each job, add them together, thus we have the max profit of all\n            * If the condition worker\'s ability > job\'s diff is wrong, and we know the remaining workers all have lower abilities (sorted) -> we had max number of valid workers\n            ** Workers that the pointer went past are the ones that have been assigned jobs, others are remaining workers with availability of receiving jobs\n        \'\'\'\n        for cur_pro, cur_diff in pro_diff: # For profit and difficulty of each job\n            valid_workers = 0 # We initially have 0 valid workers for this job and \n            while cur_wk >= 0 and worker[cur_wk] >= cur_diff: # If there\'re still worker(s) and worker\'s ability > job\'s difficulty\n                valid_workers += 1 # This `cur_wk` can do this `cur_diff` job\n                cur_wk -= 1 # Move on to next lower-ability worker\n            res += (cur_pro * valid_workers) # Adding the profit these valid workers can generate by doing this job\n        return res # Final result\n```\n\n## 4. Complexity\n- Time complexity: $$O(N + M + N * log(N) + M * log(M))$$ with `N=len(profit)`, `M=len(worker)`\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### Upvote if you find this solution helpful, thank you \uD83E\uDD0D
['Array', 'Greedy', 'Sorting', 'Python', 'Python3']