Most Profit Assigning Work LeetCode solution in Python

1
# Runtime: 489 ms (Top 13.7%) | Memory: 19.08 MB (Top 98.5%)
2

3

4
class Solution:
5
    # Time-Complexity: O(n + nlogn + n + mlog(n)) -> O((n+m) *logn)
6
    # Space-Complexity: O(n)
7
    def maxProfitAssignment(
8
        self, difficulty: List[int], profit: List[int], worker: List[int]
9
    ) -> int:
10
        # Approach: First of all, linearly traverse each and every corresponding index
11
        # position of first two input arrays: difficulty and profit to group each
12
        # item by 1-d array and put it in separate 2-d array. Then, sort the 2-d array
13
        # by increasing difficulty of the job! Then, for each worker, perform binary
14
        # search and consistently update the max profit the current worker can work and
15
        # earn! Add this value to answer variable, which is cumulative for all workers!
16
        # this will be the result returned at the end!
17
        arr = []
18
        for i in range(len(difficulty)):
19
            arr.append([difficulty[i], profit[i]])
20
        # sort by difficulty!
21
        arr.sort(key=lambda x: x[0])
22
        # then, I need to update the maximum profit up to each and every item!
23
        maximum = float(-inf)
24
        for j in range(len(arr)):
25
            maximum = max(maximum, arr[j][1])
26
            arr[j][1] = maximum
27
        ans = 0
28
        # iterate through each and every worker!
29
        for w in worker:
30
            bestProfit = 0
31
            # define search space to perform binary search!
32
            L, R = 0, len(arr) - 1
33
            # as long as search space has at least one element to consider or one job,
34
            # continue iterations of binary search!
35
            while L <= R:
36
                mid = (L + R) // 2
37
                mid_e = arr[mid]
38
                # check if current job has difficulty that is manageable!
39
                if mid_e[0] <= w:
40
                    bestProfit = max(bestProfit, mid_e[1])
41
                    # we still need to search right and try higher difficulty
42
                    # jobs that might yield higher profit!
43
                    L = mid + 1
44
                    continue
45
                else:
46
                    R = mid - 1
47
                    continue
48
            # once we break from while loop and end binary search, we should have
49
            # found bestProfit for current worker performing task that is manageable!
50
            ans += bestProfit
51
        return ans