BinarySearch 0682 Profitable Job Matching

Problem statement

https://binarysearch.com/problems/Profitable-Job-Matching/

Solution

Equal to Leetcode 0826 Most Profit Assigning Work, but change order of variable.

Complexity

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

Code

class Solution:
    def solve(self, worker, difficulty, profit):
        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.bisect(diff_prof, [w, float("inf")])
            if ind > 0: gain += diff_prof[ind-1][1]
        return gain