郑州网站设计推荐,南海网站设计,旅游网站开发系统的er图,惠新西街网站建设文章目录1. 题目2. 解题1. 题目
你打算利用空闲时间来做兼职工作赚些零花钱。
这里有 n 份兼职工作#xff0c;每份工作预计从 startTime[i] 开始到 endTime[i] 结束#xff0c;报酬为 profit[i]。
给你一份兼职工作表#xff0c;包含开始时间 startTime#xff0c;结束…
文章目录1. 题目2. 解题1. 题目
你打算利用空闲时间来做兼职工作赚些零花钱。
这里有 n 份兼职工作每份工作预计从 startTime[i] 开始到 endTime[i] 结束报酬为 profit[i]。
给你一份兼职工作表包含开始时间 startTime结束时间 endTime 和预计报酬 profit 三个数组请你计算并返回可以获得的最大报酬。
注意时间上出现重叠的 2 份工作不能同时进行。
如果你选择的工作在时间 X 结束那么你可以立刻进行在时间 X 开始的下一份工作。
示例 1
输入startTime [1,2,3,3], endTime [3,4,5,6], profit [50,10,40,70]
输出120
解释
我们选出第 1 份和第 4 份工作
时间范围是 [1-3][3-6]共获得报酬 120 50 70。示例 2
输入startTime [1,2,3,4,6], endTime [3,5,10,6,9], profit [20,20,100,70,60]
输出150
解释
我们选择第 145 份工作。
共获得报酬 150 20 70 60。示例 3
输入startTime [1,1,1], endTime [2,3,4], profit [5,6,4]
输出6提示
1 startTime.length endTime.length profit.length 5 * 10^4
1 startTime[i] endTime[i] 10^9
1 profit[i] 10^4来源力扣LeetCode 链接https://leetcode-cn.com/problems/maximum-profit-in-job-scheduling 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
先按照结束时间排序dp 是mapkey 是结束时间value 是 到结束时间 key 时的最大的收益每次二分查找 map 找到上一个不冲突的结束时间点进行状态转移
class Solution {
public:int jobScheduling(vectorint startTime, vectorint endTime, vectorint profit) {int n startTime.size();vectorint id(n);iota(id.begin(), id.end(), 0);// 生成序列 0,12。。。sort(id.begin(), id.end(),[](auto a, auto b){return endTime[a] endTime[b];//按结束时间排序});mapint,int dp;dp[0] 0;//边界dp[endTime[id[0]]] profit[id[0]];//第一个状态int ans profit[id[0]];for(int i 1; i n; i){int idx id[i];//序号auto it dp.upper_bound(startTime[idx]);//这次任务之前的不冲突任务时间点int dp_prev (--it)-second;//上一个不冲突结束时间点的最大收益dp[endTime[idx]] max(ans, max(dp[endTime[idx]], dp_prevprofit[idx]));ans max(ans, dp[endTime[idx]]);}return ans;}
};600 ms 51.9 MB C 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
