1235. Maximum Profit in Job Scheduling

link

dp[t] = end at t time, max profit

dp[t] = dp[j] + val[i] or dp (last iteration)

from sortedcontainers import SortedDict
class Solution:
    def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:

        ll = list(zip(endTime, startTime, profit))

        ll.sort(key=lambda x: x[0])

        dp = SortedDict()

        dp[-1] = 0

        res = 0
        for i in range(len(ll)):
            idx = dp.bisect_right(ll[i][1])
            current = res
            dp[ll[i][0]] = max(current, dp.peekitem(idx-1)[1] + ll[i][2]) 
            
            res = dp[ll[i][0]]


        return res