题目:
你打算利用空闲时间来做兼职工作赚些零花钱。
这里有 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]
提交通过,耶耶耶: