1. 题目
给你一个数组 events，其中 events[i] = [startDayi, endDayi] ，表示会议 i 开始于 startDayi ，结束于 endDayi 。
你可以在满足 startDayi <= d <= endDayi 中的任意一天 d 参加会议 i 。注意，一天只能参加一个会议。
请你返回你可以参加的 最大 会议数目。
示例1：
输入：events = [[1,2],[2,3],[3,4]]
输出：3
解释：你可以参加所有的三个会议。
安排会议的一种方案如上图。
第 1 天参加第一个会议。
第 2 天参加第二个会议。
第 3 天参加第三个会议。
示例 2：:
输入：events= [[1,2],[2,3],[3,4],[1,2]]
输出：4
示例 3：
输入：events = [[1,4],[4,4],[2,2],[3,4],[1,1]]
输出：4
示例 4：
输入：events = [[1,100000]]
输出：1
示例 5：
输入：events = [[1,1],[1,2],[1,3],[1,4],[1,5],[1,6],[1,7]]
输出：7
提示：
1 <= events.length <= 10^5
events[i].length == 2
1 <= events[i][0] <= events[i][1] <= 10^5来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/maximum-number-of-events-that-can-be-attended 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
2. 解题
2.1 错误解
- 先按会议的
start排序，相同的话按照end排序
class Solution {//出错代码
public:
int maxEvents(vector<vector<int>>& events) {
sort(events.begin(), events.end(),[](const auto& a, const auto& b)
{
if(a[0] == b[0])
return a[1] < b[1];
return a[0] < b[0];
});
int i, count = 0, attendTime = 0;
for(i = 0; i < events.size(); i)
{
if(attendTime < events[i][0])
{
attendTime = events[i][0];
count ;
}
else if(attendTime < events[i][1])
{
attendTime = attendTime 1;
count ;
}
}
return count;
}
};
根据出错的例子，可知上面算法有缺陷： 正确的应该是：
- 对当前会议
i，还需要往下找到j，j 被包含在i的区间内 - 如果
attendTime与区间j有交点，优先先参加j
2.2 超时解
代码语言：javascript复制class Solution {//超时代码
public:
int maxEvents(vector<vector<int>>& events) {
sort(events.begin(), events.end(),[](vector<int>& a, vector<int>& b)
{
if(a[0] == b[0])
return a[1] < b[1];
return a[0] < b[0];
});
int i, j, count = 0, attendTime = 0;
for(i = 0; i < events.size(); i)
{
if(attendTime < events[i][0])
{
attendTime = events[i][0];
count ;
attendTime ;
}
else if(attendTime <= events[i][1])
{
for(j = i 1; j < events.size() && events[i][1] <= events[j][1]; j)
;
if(j < events.size() && attendTime >= events[j][0])
{
count ;
events.erase(events.begin() j);
attendTime ;
i--;
continue;
}
count ;
attendTime ;
}
}
return count;
}
};不幸的是：最后一个例子超时
2.3 通过解
优化
- 当
attendTime与events[j]没有交点时，提前break
class Solution {//通过代码
public:
int maxEvents(vector<vector<int>>& events) {
sort(events.begin(), events.end(),[](vector<int>& a, vector<int>& b)
{
if(a[0] == b[0])
return a[1] < b[1];
return a[0] < b[0];
});
int i, j, count = 0, attendTime = 0;
for(i = 0; i < events.size(); i)
{
if(attendTime < events[i][0])
{
attendTime = events[i][0];
count ;
attendTime ;//下一个可参加的时间
}
else if(attendTime <= events[i][1])//参加时间在区间内
{
for(j = i 1; j < events.size() && events[i][1] <= events[j][1]; j)
{ //向下查找，被i包含的区间j
if(attendTime < events[j][0])
break;//如果与attendTime没有交点，后面都不可能有
}
if(j < events.size() && attendTime >= events[j][0])
{ //如果有交点，优先参加j
count ;
events.erase(events.begin() j);//参加了，删除掉
attendTime ;//下一个可能的参会时间点
i--;//后面会i ，先--i,继续跳转到原来的i进行处理
continue;
}
count ;//attendTime与j没有交点，参加会议 i
attendTime ;//时间点往后挪一个
}
}
return count;
}
};
2.4 大佬解
大佬的思路
- 按照会议
start对events升序排序 - 按日期
time进行扫描 - 将
time时开始的会议都加入到优先队列（队列存储的是会议结束end时间） - 优先队列（小顶堆）把结束日期早的先出队，参加该会议
time，新的一天，先把优先队列里已经过期的会议删除
class Solution {
public:
int maxEvents(vector<vector<int>>& events) {
sort(events.begin(), events.end());
priority_queue<int,vector<int>, greater<int>> q;//小顶堆，结束时间早的，先出队
int count = 0, i = 0, time = 0;
while(i < events.size() || !q.empty())
{
time ;
while(!q.empty() && q.top() < time)//结束时间过去了，该会议删除
q.pop();
while(i < events.size() && events[i][0] == time)
{
q.push(events[i][1]);//time时间，会议i开始了，把他的结束时间push进去
i ;
}
if(!q.empty())
{
count ;
q.pop();//最早结束的先参加
}
}
return count;
}
};
