Problem statement

https://leetcode.com/problems/most-profit-assigning-work/

Solution

Let us create diff_prof array with difficulty/profit pairs and sort it. Then we update profits we can gain: it is cumulative maximum of profits. So, now we spend O(n log n) time so far. Finally, we iterate through workers and do binary search for each worker: find the biggest gain he can have.

Complexity

Time complexity is O(n log n + Q log n), space is O(n).

Code

from bisect import bisect

class Solution:
    def maxProfitAssignment(self, difficulty, profit, worker):
        diff_prof = sorted([[i, j] for i, j in zip(difficulty, profit)])
        
        for i in range(1, len(diff_prof)):
            diff_prof[i][1] = max(diff_prof[i-1][1], diff_prof[i][1]) 
        
        gain = 0
        
        for w in worker:
            ind = bisect(diff_prof, [w, float("inf")])
            if ind > 0: gain += diff_prof[ind-1][1]
        return gain

Remark

We can do it in alternative way: iterate over sorted workers and update gain we can have for each of them. Time complexity is O(n log n + q log q).