呼和浩特做网站的,昆明网站开发推广公司,3d模拟装修设计软件,保定网站seo费用文章目录1. 题目2. 解题1. 题目
给你一个 events 数组#xff0c;其中 events[i] [startDayi, endDayi, valuei] #xff0c;表示第 i 个会议在 startDayi 天开始#xff0c;第 endDayi 天结束#xff0c;如果你参加这个会议#xff0c;你能得到价值 valuei 。 同时给你…
文章目录1. 题目2. 解题1. 题目
给你一个 events 数组其中 events[i] [startDayi, endDayi, valuei] 表示第 i 个会议在 startDayi 天开始第 endDayi 天结束如果你参加这个会议你能得到价值 valuei 。 同时给你一个整数 k 表示你能参加的最多会议数目。
你同一时间只能参加一个会议。如果你选择参加某个会议那么你必须 完整 地参加完这个会议。 会议结束日期是包含在会议内的也就是说你不能同时参加一个开始日期与另一个结束日期相同的两个会议。
请你返回能得到的会议价值 最大和 。
示例 1
输入events [[1,2,4],[3,4,3],[2,3,1]], k 2
输出7
解释选择绿色的活动会议 0 和 1得到总价值和为 4 3 7 。示例 2
输入events [[1,2,4],[3,4,3],[2,3,10]], k 2
输出10
解释参加会议 2 得到价值和为 10 。
你没法再参加别的会议了因为跟会议 2 有重叠。你 不 需要参加满 k 个会议。示例 3 输入events [[1,1,1],[2,2,2],[3,3,3],[4,4,4]], k 3
输出9
解释尽管会议互不重叠你只能参加 3 个会议所以选择价值最大的 3 个会议。提示
1 k events.length
1 k * events.length 10^6
1 startDayi endDayi 10^9
1 valuei 10^6来源力扣LeetCode 链接https://leetcode-cn.com/problems/maximum-number-of-events-that-can-be-attended-ii 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
dp[i][k] 表示 遍历完 第 i 个会议开了k次会的最大收益按结束时间排序对每个 i 会议二分查找前面最近的 无干涉的会议 j如果不存在那么就只能开会议 i如果存在就从 j 转移到 i枚举 次数还有 i 会议 不参加就从 i-1 复制过来
class Solution {
public:int maxValue(vectorvectorint events, int k) {sort(events.begin(), events.end(),[](auto a, auto b){return a[1] b[1];//结束时间排序});int n events.size();vectorvectorint dp(n, vectorint(k1, -1));// dp[i][k] 表示 遍历完 第 i 个会议开了k次会的最大收益dp[0][0] 0;dp[0][1] events[0][2];for(int i 1; i n; i)//转移到i会议查找之前可以转移过来的j{ // 二分查找时间不冲突的最晚的结束的会议 jint l 0, r i-1, mid, j n;while(l r){mid l((r-l)1);if(events[mid][1] events[i][0])//时间冲突r mid-1;else{if(midn-1 || events[mid1][1] events[i][0]){j mid;break;}elsel mid1;}}// i 会议不开for(int t 0; t k; t)dp[i][t] max(dp[i][t], dp[i-1][t]);// 没有可以转移到 i 的会议if(j n) //只能开一个会议idp[i][1] max(dp[i][1], events[i][2]);else // j 可以转移到 i 会议for(int t 0; t k; t)//原来开了多少次会{dp[i][t1] max(dp[i][t1], dp[j][t]events[i][2]);}}int ans 0;for(int t 0; t k; t)ans max(ans, dp[n-1][t]);return ans;}
};1764 ms 238.1 MB C 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
