Maximum Profit in Job Scheduling LeetCode solution in Python

1
# Runtime: 990 ms (Top 41.71%) | Memory: 47.5 MB (Top 21.04%)
2
class Solution:
3
    def jobScheduling(
4
        self, startTime: List[int], endTime: List[int], profit: List[int]
5
    ) -> int:
6
        n = len(startTime)
7
        jobs = list(zip(startTime, endTime, profit))
8
        jobs.sort()
9
        startTime.sort()
10

11
        @lru_cache(None)
12
        def recur(i):
13
            if i == n:
14
                return 0
15
            j = bisect_left(startTime, jobs[i][1])
16
            one = jobs[i][2] + recur(j)
17
            two = recur(i + 1)
18
            return max(one, two)
19

20
        return recur(0)