题目描述
给你一个 events
数组,其中 events[i] = [startDayi, endDayi, valuei]
,表示第 i
个会议在 startDayi
天开始,第 endDayi
天结束,如果你参加这个会议,你能得到价值 valuei
。同时给你一个整数 k
表示你能参加的最多会议数目。
你同一时间只能参加一个会议。如果你选择参加某个会议,那么你必须 完整 地参加完这个会议。会议结束日期是包含在会议内的,也就是说你不能同时参加一个开始日期与另一个结束日期相同的两个会议。
请你返回能得到的会议价值 最大和 。
样例
输入:events = [[1,2,4],[3,4,3],[2,3,1]], k = 2
输出:7
解释:选择绿色的活动会议 0 和 1,得到总价值和为 4 + 3 = 7 。
输入:events = [[1,2,4],[3,4,3],[2,3,10]], k = 2
输出:10
解释:参加会议 2 ,得到价值和为 10 。
你没法再参加别的会议了,因为跟会议 2 有重叠。你 不 需要参加满 k 个会议。
输入: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
算法分析
1、对所有区间按照右端点进行排序
2、如图所示
时间复杂度 $O(nklogn)$
参考文献
y总
C++ 代码
const int N = 1000010;
struct Edge {
int l, r, v;
bool operator < (const Edge &t) const {
return r < t.r;
}
}q[N];
class Solution {
public:
int maxValue(vector<vector<int>>& events, int k) {
int n = events.size();
vector<vector<int>> f(n + 1, vector<int> (k + 1));
for(int i = 1;i <= n;i ++)
{
q[i] = {events[i - 1][0], events[i - 1][1], events[i - 1][2]};
}
sort(q + 1, q + n + 1);
for(int i = 1;i <= n;i ++)
for(int j = 1;j <= k;j ++)
{
f[i][j] = f[i - 1][j];
//找到满足小于第i个区间的左端点的最大区间
int l = 0, r = i - 1;
while(l < r)
{
int mid = l + r + 1 >> 1;
if(q[mid].r < q[i].l) l = mid;
else r = mid - 1;
}
f[i][j] = max(f[i][j], f[l][j - 1] + q[i].v);
}
return f[n][k];
}
};