Python - O(N^2) ➜ O(NLogN) | EXPLAINED
1. BRUTE FORCE - O(N^2)\n\nIn the Brute Force approach, for every worker, we go through every difficulty and if the worker can do that job, we check if it can g
## **1. BRUTE FORCE - O(N^2)**\n\nIn the Brute Force approach, for every worker, we go through every difficulty and if the worker can do that job, we check if it can give him a profit greater than previous job. If yes, update the maximum profit for that worker.\n\nIn the end, we add this maximum profit to the final output that we have to return.\n\nThe issue is that the arrays can be of up to 10^4 length. So, an O(N^2) solution will fail for large inputs and will show TLE.\n\nBut from this solution, we can start thinking about the Optimized Approach.\n\n    def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:\n        \n        maxProfit = 0\n        \n        m = len(worker)\n        n = len(difficulty)\n        \n        # For every worker, find the maximum profit that he can get (if possible)\n        for j in range (m):\n            maxWorkerProfit = 0\n            # Go through each job difficulty\n            for i in range(n):\n                # And if we find a difficulty <= ability of worker\n                # Then we need to update the profit \n                # if this job gives a higher profit than previous job\n                if difficulty[i] <= worker[j]:\n                    maxWorkerProfit = max(maxWorkerProfit, profit[i])\n            \n            # And when we found the maximum profit for this worker, just add it to the output that we need to return\n            maxProfit += maxWorkerProfit\n        \n        \n        return maxProfit\n\t\t\n## **2. BINARY SEARCH APPROACH - O(NLogN)**\n\nThe reason of O(N^2) complexity in Brute Force approach is that inner loop. For every worker, we have to iterate from the beginning to the end to find the maximum profit. \n\n\tBut what if the difficulties were in sorted order already?\n\nIn that case, if a worker is able to do any job with difficulty[i], then we can say that he can also do any job that has a lower difficulty right? In other words, in that case, we don\'t worry about the difficulties on left side as they will all be valid as the array is sorted. And that\'s the idea of Binary Search. \n\nSo using Binary Search, all we have to do is find the rightmost valid difficulty out of the sorted difficulty list. Once we can find that, then all we need to find is what is the maximum profit that we can get in the [0, rightmost valid difficulty index] range. And to avoid calculating this for every worker, we can precomute this before we even apply Binary Search. \n\nBut there is one issue with this approach and I was stuck at this for almost half an hour before I realised that I made a dumb mistake.\n\nNotice that "difficulty" and "profit" are in sync. That means, ith difficulty has profit[i] profit. So if we only sort difficulty list, the profit list remains unchanged and that will not give us correct result. We cannot sort these two lists separately as well. Because profit of a job with a higher difficulty might be less than profit of a job with lower difficulty. So sorting them separately will also give wrong results.\n\nAnd so, we want a way such that when we sort the "difficulty" list, the "profit" list is still in sync. And for that, we can make a new list in which at every index, we have a pair of (difficulty, profit). So now, even if we sort this new list based on difficulty value, the profit value will always stay with its correct corresponding difficulty, just as it was initially in the input lists.\n\n*You will find a lot of questions that have a similar pattern and they might differ in only the way we precompute max value. For some problems, you have to find maximum on right side whereas for some you have to find maximum on left side of each index. That depends on the problem statement. For example here, we know that if one difficulty is valid, all difficulties less than it are also valid. Hence we precomputed the maximum value on left side of each index.*\n\n```\ndef maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:\n        \n        maxProfit = 0\n        \n        m = len(worker)\n        n = len(difficulty)\n        \n        # We cannot just sort difficulty array\n        # We also need to make sure profit array is in same order as difficulty array\n        # So what we can do is at each index, we can keep what is the difficulty of a job and what is its profit\n        jobs = []\n        for i in range(n): jobs.append((difficulty[i], profit[i]))\n            \n        # Now we can sort this new list we made and since difficulty is the first value in each tuple\n        # this list will be sorted based on difficulty\n        jobs.sort()\n        \n        # Precompute maximum profit on left for each index\n        maxProfitSoFar = [0] * n\n        \n        # For first index, maximum profit on left will be profit at its index only\n        maxProfitSoFar[0] = jobs[0][1]\n        for i in range(1, n): maxProfitSoFar[i] = max(maxProfitSoFar[i - 1], jobs[i][1])           \n\n        # For every worker, find the maximum profit that he can get (if possible)\n        for j in range(m):\n            maxWorkerProfit = 0\n            \n            # Instead of linear search, we can now apply Binary Search here\n            # As we have sorted the difficulty\n            # Since difficulty is sorted, all we want to find is the rightmost valid index in difficulty array\n            # That is the rightmost index at which difficulty is <= ability of the worker\n            \n            start = 0\n            end = n - 1\n            rightmostIndex = -1\n            \n            \n            while start <= end:\n                mid = start + (end - start) // 2\n                \n                # If job at mid can be done by worker\n                # Then this is one possible solution\n                # But we want rightmost valid difficulty\n                # So we keep searching on right side of mid\n                if jobs[mid][0] <= worker[j]:\n                    rightmostIndex = mid\n                    start = mid + 1 \n                # If job at mid cannot be done by the worker\n                # That means, no job after mid can be done as well\n                # Since array is now sorted\n                else: end = mid - 1\n            \n            # Now, as we have precomputed maximum profit till each index already\n            # We can find the maximum profit till rightmostIndex in O(1) time\n            if rightmostIndex != -1: maxWorkerProfit = maxProfitSoFar[rightmostIndex]\n                \n            # And append that to the final output that we need to return\n            maxProfit += maxWorkerProfit\n            \n        \n        return maxProfit\n```\n\n
['Binary Search', 'Python']