給定一堆job的開始、結(jié)束時(shí)間以及收益，問如何規(guī)劃可以獲得最大收益
類似0-1背包問題，但因?yàn)橛虚_始、結(jié)束時(shí)間的限制，所以不需要每次查找所有job，利用二分來搜索符合條件的job
具體步驟：
1.將所有job按照開始時(shí)間從早到晚排序
2.從最后一個(gè)job向前遍歷，dp[i]存儲(chǔ)開始時(shí)間>=job i的結(jié)束時(shí)間的所有已經(jīng)安排好的job的最大收益只和，用二分查找搜索開始時(shí)間比當(dāng)前job i結(jié)束時(shí)間更大（或者相等）的job的最小下標(biāo) j，dp更新方程：
dp[i] = max(dp[i + 1], dp[j] + jobs[i][2])
3.最后輸出dp[0]
1 #1235
2 #Runtime: 1113 ms
3 #Memory Usage: 25.8 MB
4
5 class Solution(object):
6 def jobScheduling(self, startTime, endTime, profit):
7 """
8 :type startTime: List[int]
9 :type endTime: List[int]
10 :type profit: List[int]
11 :rtype: int
12 """
13 jobs, n = sorted(zip(startTime, endTime, profit)), len(startTime)
14 S = [i[0] for i in jobs]
15 dp = [0] * (n + 1)
16 for i in range(n - 1, -1, -1):
17 j = bisect_left(S, jobs[i][1])
18 dp[i] = max(dp[i + 1], dp[j] + jobs[i][2])
19 return dp[0]
當(dāng)然，也可以按照job的結(jié)束時(shí)間排序，這樣的話步驟為：
1.將所有job按照結(jié)束時(shí)間從早到晚排序
2.從第一個(gè)job向后遍歷，dp[i]存儲(chǔ)結(jié)束時(shí)間<=job i的開始時(shí)間的所有已經(jīng)安排好的job的最大收益只和，用二分查找搜索結(jié)束時(shí)間比當(dāng)前job i開始時(shí)間更小（或者相等）的job的最大下標(biāo) j，dp更新方程：
dp[i] = max(dp[i - 1], dp[j] + jobs[i - 1][2]) （這里jobs[i - 1][2]下標(biāo)i-1是因?yàn)閖ob的下標(biāo)從0開始，而dp的下標(biāo)1～n，dp[0]用于存儲(chǔ)base）
3.最后輸出dp[n]
1 #1170
2 #Runtime: 1170 ms
3 #Memory Usage: 25.9 MB
4
5 lass Solution(object):
6 def jobScheduling(self, startTime, endTime, profit):
7 """
8 :type startTime: List[int]
9 :type endTime: List[int]
10 :type profit: List[int]
11 :rtype: int
12 """
13 jobs, n = sorted(zip(endTime, startTime, profit)), len(startTime)
14 S = [i[0] for i in jobs]
15 dp = [0] * (n + 1)
16 for i in range(1, n + 1):
17 j = bisect_right(S, jobs[i - 1][1])
18 dp[i] = max(dp[i - 1], dp[j] + jobs[i - 1][2])
19 return dp[n]