1235. Maximum Profit in Job Scheduling
这季profit会超强，强到不行，火力全开的那种
虽然Staff都很操就是了，工程师们辛苦啦
后面还有接续的jobs要弄，不知道如何
因为想不到要怎么讲所以这样最快，就请好好享受
(蛤?
给你很多 jobs 的起始和结束时间，请你找出最大的 profit。
Example 1:
https://assets.leetcode.com/uploads/2019/10/10/sample1_1584.png
Input: startTime = [1,2,3,3], endTime = [3,4,5,6], profit = [50,10,40,70]
Output: 120
思路:
1.可以先想要怎么决定每个 job 要不要做 可以先定义 dp[t] 代表 t 时间点的最佳解
如果做了就代表从他开始到结束时都没有做其他的 job
所以 profit 就是 dp[job开始] + job的profit
然后看这个值有没有办法去更新 dp[job结束]
如果不需要这个 job 就代表 t=job开始~job结束 中有比他更大的 dp[t]
2.实际上并不需要去 iterate job开始到job结束中所有的 t 值
可以用 sweep line 先存所有事件点 排序 再从左到右扫一遍就好
这样就只需要存每个事件点的最佳解就好
所以流程就是扫事件点 遇到 job 开始就把目前的最佳解记下来 (代表dp[job开始])
遇到 job 结束就把刚刚存的最佳解拿出来加上 profit 看能不能更新目前的最佳解
3.Python code:
class Solution:
def jobScheduling(self, startTime: List[int], endTime: List[int], profit:
List[int]) -> int:
events = []
n = len(startTime)
for i in range(n):
events.append([startTime[i], 1, i])
events.append([endTime[i], 0, i])
events.sort()
dp = {}
res = 0
for event in events:
if event[1] == 1:
dp[event[2]] = res
else:
res = max(res, dp[event[2]]+profit[event[2]])
return res