1235. Maximum Profit in Job Scheduling

Notes 2022:

加入dfs + cache 的做法

class Job:
    def __init__(self, startTime: int, endTime: int, profit: int):
        self.startTime = startTime
        self.endTime = endTime
        self.profit = profit

class Solution:
    def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
        n = len(startTime)
        
        jobs = []
        for i in range(n):
            job = Job(startTime[i], endTime[i], profit[i])
            jobs.append(job)
        jobs.sort(key = lambda job: job.startTime)
        
        startTime = [job.startTime for job in jobs]
        cache = [-1 for _ in range(n)] 
        
        return self.findMaxProfit(jobs, startTime, cache, 0)
    
    def findMaxProfit(self, jobs: List[Job], startTime: List[int], cache: List[int], idx: int) -> int:
        if idx == len(jobs):
            return 0
        
        if cache[idx] != -1:
            return cache[idx]
        
        nextIdx = bisect.bisect_left(startTime, jobs[idx].endTime)
        includeIdxProfit = jobs[idx].profit + self.findMaxProfit(jobs, startTime, cache, nextIdx)
        excludeIdxProfit = self.findMaxProfit(jobs, startTime, cache, idx+1)
        cache[idx] = max(includeIdxProfit, excludeIdxProfit)
        return cache[idx]

=============================================

Option 1: DP + binary search T = O(n log n)

0, 1 knapsack

We can either sort the array by start time or end time

sort by start time
- to leverage binary search, we need to use end time to compare with sorted start time
- This can give us the index of the next available job j
- form relationship between dp[i] and dp[j] where i < j
- dp[i] is the max profit you can make with using subarray [i ... n-1]. job[i] may not be selected to get dp[i]
sort by end time
- to leverage binary search, we need to use start time to compare with sorted end time
- This can give us the index of the last available job j
- form relationship between dp[i] and dp[j] where i > j
- dp[i] is the max profit you can make with using subarray [0 ... i]. job[i] may not be selected to get dp[i]

class Solution:
    def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
        n = len(startTime)
        startTime, endTime, profit = zip(*sorted(zip(startTime, endTime, profit)))
        
        dp = [0] * (n+1)
        for i in range(n-1, -1, -1):
            j = bisect.bisect_left(startTime, endTime[i])
            dp[i] = max(dp[i+1], profit[i] + dp[j])
        return dp[0]

class Solution:
    def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
        n = len(startTime)
        startTime, endTime, profit = zip(*sorted(zip(startTime, endTime, profit), key=lambda job: job[1]))
        
        dp = [0]
        for i in range(n):
            j = bisect.bisect_right(endTime, startTime[i]) 
            dp.append(max(dp[-1], profit[i] + dp[j]))
        return dp[-1]

Option 2: DP T = O(N^2)

class Solution:
    def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
        n = len(startTime)
        jobs = []
        for i in range(n):
            jobs.append((startTime[i], endTime[i], profit[i]))
        jobs.sort()
        
        dp = [job[2] for job in jobs]
    
        res = 0
        for i in range(n):
            for j in range(i):
                if jobs[j][1] <= jobs[i][0]:
                    dp[i] = max(dp[i], dp[j] + jobs[i][2])
            res = max(res, dp[i])
        return res

1235. Maximum Profit in Job Scheduling - cocoder39/coco39_LC GitHub Wiki