1235 Maximum Profit in Job Scheduling

https://leetcode.com/problems/maximum-profit-in-job-scheduling/

solution

# dp[i]: max(包含本job利润，不包含本job利润)，包含时需要用二分查找从前面job中找到开始时间不冲突的

class Solution:
    def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
        jobs = sorted(zip(endTime, startTime, profit))
        number_of_jobs = len(profit)
        
        dp = [0] * (number_of_jobs + 1)
        for i, (current_end_time, current_start_time, current_profit) in enumerate(jobs):
            index = bisect.bisect_right(jobs, current_start_time, hi=i, key=lambda x: x[0])
            dp[i + 1] = max(dp[i], dp[index] + current_profit)
        return dp[number_of_jobs]

时间复杂度：O(nlog(n)) 空间复杂度：O(n)