LeetCode 我的日程安排表III（细节处理）
实现一个 MyCalendar 类来存放你的日程安排，你可以一直添加新的日程安排。
MyCalendar 有一个 book(int start, int end)方法。它意味着在start到end时间内增加一个日程安排，注意，这里的时间是半开区间，即 [start, end), 实数 x 的范围为， start <= x < end。
当 K 个日程安排有一些时间上的交叉时（例如K个日程安排都在同一时间内），就会产生 K 次预订。
每次调用 MyCalendar.book方法时，返回一个整数 K ，表示最大的 K 次预订。
请按照以下步骤调用MyCalendar 类: MyCalendar cal = new MyCalendar(); MyCalendar.book(start, end)
示例 1:
MyCalendarThree();
MyCalendarThree.book(10, 20); // returns 1
MyCalendarThree.book(50, 60); // returns 1
MyCalendarThree.book(10, 40); // returns 2
MyCalendarThree.book(5, 15); // returns 3
MyCalendarThree.book(5, 10); // returns 3
MyCalendarThree.book(25, 55); // returns 3
解释:
前两个日程安排可以预订并且不相交，所以最大的K次预订是1。
第三个日程安排[10,40]与第一个日程安排相交，最高的K次预订为2。
其余的日程安排的最高K次预订仅为3。
请注意，最后一次日程安排可能会导致局部最高K次预订为2，但答案仍然是3，原因是从开始到最后，时间[10,20]，[10,40]和[5,15]仍然会导致3次预订。
说明:
每个测试用例，调用 MyCalendar.book 函数最多不超过 400次。
调用函数 MyCalendar.book(start, end)时， start 和 end 的取值范围为 [0, 10^9]。
思路分析： 请先翻阅 LeetCode 我的日程安排表II（细节处理），下面的代码均是上一题的修改！
这道题与上一题基本一样，我们只要使用一个计数器记录当前日程表中最大安排次数即可。
//每个时间段程序表示[start, end],注意与题中[start, end)中右区间的闭合差异
struct Agenda {
int start;//时间段起始时刻
int end;//时间段结束时刻
int cnt;//这个时间段已经安排的日程数
Agenda(){}
Agenda(int _start, int _end, int _cnt = 1) {
start = _start;
end = _end;
cnt = _cnt;
}
};
class MyCalendarThree {
public:
int maxCnt = 1;//整个日程表中时间段安排次数最多的次数初始化为1
list<Agenda> myList;//升序存储整个日程表
MyCalendarThree() {
}
int book(int start, int end) {
auto it = myList.begin();
//第一步：查找list中第一个与[start, end - 1]有交集的时间段的迭代器
while (it != myList.end() && it->end < start) {
++it;
}
if (it == myList.end() || it->start >= end) {
//如果在list中没有找到与[start, end - 1]有交集的时间段（包括list的首、尾端，以及list中两个时间段的中间），则直接插入
myList.insert(it, Agenda(start, end - 1));
return maxCnt;//插入次数为1的时间段并不是更新最大值
}
//第二步：将[start, end - 1]插入到list中，对于已经在list的部分，直接将cnt自增，不在cnt的部分插入
while (start < end) {
if (it == myList.end() || it->start >= end) {
//第一种情况：当前it与[start, end - 1]没有有交集则直接插入，比如[6,7]插入[[4,5],[10,11]]
myList.insert(it, Agenda(start, end - 1));
start = end;//更新剩余的时间段为[end - 1,end - 1]，因为刚刚已经把所有区间都插入了
}
else if (start < it->start) {
//第二种情况：当前[start, end - 1]在it之前还有一部分，比如[1,7]插入[[4,5],[10,11]],[1,7]在[4,5]之前还有[1,3]这一部分需要插入
it = myList.insert(it, Agenda(start, it->start - 1));
++it;
start = it->start;//更新剩余的时间段为[4, 7](因为[1,3]已经插入)
}
else if (start == it->start) {
//第三种情况：当前[start, end - 1]与it起始部分重叠，有[4,4]或者[4,7]两种可能性插入[[4,5],[10,11]]
maxCnt = max(maxCnt, it->cnt + 1);//只有这种情况需要更新最大值
if (end <= it->end) {
//处理[4,4]插入[[4,5],[10,11]]这种情况
it = myList.insert(it, Agenda(start, end - 1, it->cnt + 1));
++it;
it->start = end;
start = end;//已经插入完毕
}
else {
//处理[4,7]插入[[4,5],[10,11]]这种情况
it->cnt += 1;//it([4,5])这一段安排的次数自增，
start = it->end + 1;//已经插入[4,5]剩余[6, 7]
++it;
}
}
else {
//第四种情况：当前[start, end - 1]与it末端重叠，比如[5,7]插入[[4,5],[10,11]],
it = myList.insert(it, Agenda(it->start, start - 1, it->cnt));//我们先将[4,5]拆分成[4,4],[5,5]因为[5,5]即将安排两次，（注意Agenda构造函数第三个参数是it->cnt，[4,5]安排多少次[4,4]就安排了多少次）
++it;
it->start = start;//此时并没缩小[start,end - 1]蛋式下一次循环将会跳到第三种情况处理
}
}
return maxCnt;
}
};
/**
* Your MyCalendarThree object will be instantiated and called as such:
* MyCalendarThree* obj = new MyCalendarThree();
* int param_1 = obj->book(start,end);
*/
最快的都要175ms+，非常开森