给定一堆job的开始、结束时间以及收益，问如何规划可以获得最大收益
类似0-1背包问题，但因为有开始、结束时间的限制，所以不需要每次查找所有job，利用二分来搜索符合条件的job
具体步骤：
1.将所有job按照开始时间从早到晚排序
2.从最后一个job向前遍历，dp[i]存储开始时间>=job i的结束时间的所有已经安排好的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的开始时间的所有已经安排好的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]