LC 1235 [H] Maximum Profit in Job Scheduling - ALawliet/algorithms GitHub Wiki

class Solution:
    def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
        N = len(startTime)
        jobs = list(zip(startTime, endTime, profit))
        jobs.sort()
        startTime.sort() # optimization
        
        @cache
        def rec(i):
            if i==N: return 0
            
            # j=i+1 ; while j<N and jobs[i][1] > jobs[j][0]: j += 1
                
            j = bisect_left(startTime,jobs[i][1]) # optimization
                
            one = jobs[i][2]+rec(j) # take it and go next
            two = rec(i+1) # skip it
            return max(one,two)
        return rec(0)
    
    def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:

        # print(zip(startTime,endTime,profit))
        # print(sorted(zip(startTime,endTime,profit)))
        # print(*sorted(zip(startTime,endTime,profit)))
        # print(zip(sorted(zip(startTime,endTime,profit))))
        # print(zip(*sorted(zip(startTime,endTime,profit))))
        # zip the three, then sort by startTime, then * to unpack them as separate lists, then re-zip them
        start,end,profits = zip(*sorted(zip(startTime,endTime,profit)))

        #for each start time, mapp them to next endtime using binseach
        jump = {j: bisect_left(start, end[j]) for j in range(len(start))}

        #rec(i) = max(profit[i] + rec(i), rec(i+1))
        # memo = {}

        @cache
        def rec(i):
            if i == len(start):
                return 0 #we are done, no more profit
            # if i in memo:
                # return memo[i]
            take = profits[i] + rec(jump[i])
            no_take = rec(i+1)
            res = max(take,no_take)
            # memo[i] = res
            return res

        return rec(0)