BinarySearch 0486 Job Scheduling to Maximize Profit

Problem statement

https://binarysearch.com/problems/Job-Scheduling-to-Maximize-Profit/

Solution

Equal to Leetcode 1235 Maximum Profit in Job Scheduling.

Complexity

It is O(n log n) for time and O(n) for space.

Code

class Solution:
    def solve(self, jobs):
        jobs = sorted(jobs)
        S = [i[0] for i in jobs]
        n = len(jobs)
        dp = [0] * (n + 1)
        for k in range(n-1,-1,-1):
            temp = bisect_left(S, jobs[k][1])
            dp[k] = max(jobs[k][2] + dp[temp], dp[k+1])
        return dp[0]