规划兼职工作
题目
你打算利用空闲时间来做兼职工作赚些零花钱。
这里有 n 份兼职工作,每份工作预计从 startTime[i] 开始到 endTime[i] 结束,报酬为 profit[i]。
给你一份兼职工作表,包含开始时间 startTime,结束时间 endTime 和预计报酬 profit 三个数组,请你计算并返回可以获得的最大报酬。
注意,时间上出现重叠的 2 份工作不能同时进行。
如果你选择的工作在时间 X 结束,那么你可以立刻进行在时间 X 开始的下一份工作。
复制代码
题解
看标签提示 DP
首先 按 endTime 排序,因为要根据这个来判断这个兼职能不能做
非递减排序
jobs.sort((a, b) => a[1] - b[1]);
dp[x] 表示前 x 份兼职可以获取的最大报酬
初始化 dp[0] = 0
i>0: dp[i] = max(dp[i - 1], dp[k] + profit[i - 1])
k 表示干第 i 个兼职时能干的上一次兼职
max(第 i 个不干,干第 i 个)
然后关键就是找 k 了,k 要满足的要求就是 结束时间小于等于第 i 份工作的开始时间的最近一次兼职,这里可以用二分查找来优化 —— 注意是找右侧边界——这个写法要注意
注意下标为 i-1 的时候是第 i 份工作
JS 实现:
复制代码
版权声明: 本文为 InfoQ 作者【掘金安东尼】的原创文章。
原文链接:【http://xie.infoq.cn/article/c05dbd4812caf8b81e08ee3dc】。文章转载请联系作者。
评论