题目：

你打算利用空闲时间来做兼职工作赚些零花钱。

这里有 n 份兼职工作，每份工作预计从 startTime[i] 开始到 endTime[i] 结束，报酬为 profit[i]。

给你一份兼职工作表，包含开始时间 startTime，结束时间 endTime 和预计报酬 profit 三个数组，请你计算并返回可以获得的最大报酬。

注意，时间上出现重叠的 2 份工作不能同时进行。

如果你选择的工作在时间 X 结束，那么你可以立刻进行在时间 X 开始的下一份工作。

提示：

• 1 <= startTime.length == endTime.length == profit.length <= 5 * 10^4
• 1 <= startTime[i] < endTime[i] <= 10^9
• 1 <= profit[i] <= 10^4

思考：

解法一——动态规划（以时间作为划分）

设f(x)为在时间为x时能获得的最大报酬，

设正好在x结束的工作开始于时间m，报酬为p，那么

f(x) = max(f(x-1), f(m_1)+p_1, f(m_2)+p_2, ......) 

代码如下：

class Solution:
    def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
        # 动态规划：dp[i]表示在时间为i时能获得的最大报酬
        # f(x) = max(f(x-1), f(m)+p)   设正好在x结束的所有工作开始于m，报酬为p
        n = max(endTime)
        dp = [0 for _ in range(n+1)]
        for i in range(2, n+1):
            candidate = []  # 记录所有"f(m)+p"
            for index, value in enumerate(endTime):
                if value == i:
                    candidate.append(dp[startTime[index]] + profit[index])
            if candidate:
                dp[i] = max(dp[i - 1], max(candidate))
            else:
                dp[i] = dp[i - 1]
        return dp[n]
            

超时，卡在第 21 / 35 个例子：

 

优化 

可以将遍历endtime数组找到刚好在x结束的所有工作这一步提到最前面，避免每次计算f(x)时都要遍历一次。代码如下：

from collections import defaultdict
class Solution:
    def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
        # 动态规划：dp[i]表示在时间为i时能获得的最大报酬
        # f(x) = max(f(x-1), f(m)+p)   设正好在x结束的所有工作开始于m，报酬为p
        n = max(endTime)
        dp = [0 for _ in range(n+1)]
        end_index = defaultdict(list)   # 键为结束时间，值为这份工作的索引
        for index, time in enumerate(endTime):
            end_index[time].append(index)

        for i in range(2, n+1):
            if not end_index[i]:
                dp[i] = dp[i - 1]
            else:
                candidate = []  # 记录所有"f(m)+p"
                for index in end_index[i]:
                    candidate.append(dp[startTime[index]] + profit[index])
                dp[i] = max(dp[i - 1], max(candidate))

        return dp[n]

时间上确实加快了，但是卡在一个特殊的测试例子上，超内存了：

原因是只有四项工作待选，但是用时间划分的话，dp数组的长度有1000000001，显然在这种情况下仍然按时间划分造成了内存极大浪费。

解法二——动态规划（以工作作为划分）

那么换一个思路，将所有工作按结束时间排序，以是否选择每一项工作作为划分。

设f(x)表示在第x个结束的工作结束时，能获得的最大报酬，即 选择工作x 或者 不选择工作x 这两种决策得到的报酬更大值。公式如下，其中y是满足endtime(y) <= starttime(x) 条件的工作索引最大值，如果不存在这样的y，则f(y)取0：

 f(x) = max(f(x-1), f(y)+profit(x))

为了减少耗时，这里找y使用二分查找。代码如下：

from collections import defaultdict
class Solution:
    def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
        # 动态规划：f(x)表示在第x个结束的工作结束时，能获得的最大报酬，即 选择工作x 或者 不选择工作x 的报酬更大值
        # 公式如下，其中y是满足endtime(y) <= starttime(x) 条件的工作索引最大值，如果不存在这样的y，则f(y)取0
        # f(x) = max(f(x-1), f(y)+profit(x))

        # 将所有工作按结束时间排序
        combined_list = list(zip(startTime, endTime, profit))
        combined_list = sorted(combined_list, key = lambda x : x[1])
        n = len(profit)
        dp = [-1 for _ in range(n)]
        dp[0] = combined_list[0][2]
        for x in range(1, n):
            # 找到工作y：满足endtime(y) <= starttime(x) 条件的最大值
            left = 0
            right = x - 1
            f_y = 0
            while left <= right:
                mid = (left + right) // 2
                if combined_list[mid][1] <= combined_list[x][0]:
                    f_y = dp[mid]
                    left = mid + 1
                else:
                    right = mid - 1
            # f(x) = max(f(x-1), f(y)+profit(x))
            dp[x] = max(dp[x-1], f_y + combined_list[x][2])

        return dp[n-1]

提交通过，耶耶耶：