給定一堆job的開始、結束時間以及收益，問如何規(guī)劃可以獲得最大收益
類似0-1背包問題，但因為有開始、結束時間的限制，所以不需要每次查找所有job，利用二分來搜索符合條件的job
具體步驟：
1.將所有job按照開始時間從早到晚排序
2.從最后一個job向前遍歷，dp[i]存儲開始時間>=job i的結束時間的所有已經(jīng)安排好的job的最大收益只和，用二分查找搜索開始時間比當前job i結束時間更大（或者相等）的job的最小下標 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]
當然，也可以按照job的結束時間排序，這樣的話步驟為：
1.將所有job按照結束時間從早到晚排序
2.從第一個job向后遍歷，dp[i]存儲結束時間<=job i的開始時間的所有已經(jīng)安排好的job的最大收益只和，用二分查找搜索結束時間比當前job i開始時間更小（或者相等）的job的最大下標 j，dp更新方程：
dp[i] = max(dp[i - 1], dp[j] + jobs[i - 1][2]) （這里jobs[i - 1][2]下標i-1是因為job的下標從0開始，而dp的下標1～n，dp[0]用于存儲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]