题目:
你打算利用空闲时间来做兼职工作赚些零花钱。
这里有 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, ......)
代码如下:
python">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,报酬为pn = 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)时都要遍历一次。代码如下:
python">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,报酬为pn = 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使用二分查找。代码如下:
python">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 = 0right = x - 1f_y = 0while left <= right:mid = (left + right) // 2if combined_list[mid][1] <= combined_list[x][0]:f_y = dp[mid]left = mid + 1else: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]
提交通过,耶耶耶: