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