题目
?
思路
解题思路
看了很久别人的思路，大都用线段树解决日程安排问题，但是想了很久都想不明白怎么用线段树解决日程安排，总觉得线段树维护十分困难，有会的大佬可以评论区指点一下
既然不会线段树解决，那就想别的方法解决
双数组思路
解决所有日程安排问题
- 729.我的日程安排|
- 731.我的日程安排||
- 732.我的日程安排|||
对于所有日程安排问题，不管题目具体问法，都会涉及一个相同的元素日程的开始时间和结束时间，那么对于任意日程问题，我们都可以申请一个一样的结构体
typedef struct {
? ? int startCnt;//左边界下标
? ? int endCnt;//右边界下标
? ? int start[max]; // 左边界
? ? int end[max]; // 右边界
} MyCalendar;
分别保存每一个日程的开始时间和结束时间，每加入一个新的日程，都会产生两个相同的问题?
- 当前日程时间与已经存在的日程时间冲突
- 当前日程时间与已经存在的日程时间不冲突
具体如何处理这两个问题，具体问题会有具体要求
- 729.我的日程安排|
- 题目要求当加入的日程与已经存在的日程冲突超过两次时(本身也算一个有效日程)，将此次日程不存入并且返回false
- 731.我的日程安排||
- 题目要求当加入的日程与已经存在的日程冲突超过三次时，将此次日程不存入并且返回false
- 732.我的日程安排|||
- 题目要求每加入一个日程，返回加入日程与已经存在的日程冲突最大的次数
每个题目的大概思路都可以表示为，当来一个新日程时，我们先将日程加入对应数组中，然后求此时数组中的冲突数，当冲突数不满足要求时，结束并且将刚刚加入当数组中的日程踢出(删除)，以此类推，始终维持数组中的最大冲突数满足题目要求。
如何计算加入的日程或已经存在的日程的冲突个数
这个时候我们保存的日程开始与结束数组就要发挥作用了，将日程加入数组之后，将保存了日程安排的数组进行升序排列，然后遍历日程数组当 obj->start[i] < obj->end[j] 时，冲突的日程(自身与自身也是冲突的) +1，否则冲突的日程 -1。升序处理会破坏原来日程安排时间，但是我们关心的时间是否有冲突，并不关心具体时间如何安排。
?
对于具体的问题只需要在次思路基础之上简单调整一下即可
代码
729.我的日程安排|
typedef struct {
int startCnt;//左边界下标
int endCnt;//右边界下标
int start[1000]; // 左边界
int end[1000]; // 右边界
} MyCalendar;
MyCalendar* myCalendarCreate() {
MyCalendar * obj = (MyCalendar *)malloc(sizeof(MyCalendar));
memset(obj, 0, sizeof(MyCalendar));
return obj;
}
//快排子函数,升序
int compare(const int *a, const int *b)
{
return a[0] > b[0] ? 1 : -1;
}
bool myCalendarBook(MyCalendar* obj, int start, int end) {
// 插入新节点
obj->start[obj->startCnt++] = start;
obj->end[obj->endCnt++] = end;
// 左、右边界排序
qsort(obj->start, obj->startCnt, sizeof(obj->start[0]), compare);
qsort(obj->end, obj->endCnt, sizeof(obj->end[0]), compare);
int i = 0;
int j = 0;
int tmp = 0;
while (i < obj->startCnt && j < obj->endCnt) {
if(obj->start[i] == -1)//删除的元素位置，
{
i++;
j++;
continue;
}
if (obj->start[i] < obj->end[j]) {//计算冲突数
tmp++;
i++;
} else {
tmp--;
j++;
}
if(tmp == 2)
{
for(int m = 0; m < obj->startCnt; m++)//将原来加入的start删除
{
if(obj->start[m] == start)
{
obj->start[m] = -1;
break;
}
}
for(int m = 0; m < obj->startCnt; m++)//将原来加入的end删除
{
if(obj->end[m] == end)
{
obj->end[m] = -1;
break;
}
}
return false;
}
}
return true;
}
void myCalendarFree(MyCalendar* obj) {
free(obj);
}
/**
* Your MyCalendar struct will be instantiated and called as such:
* MyCalendar* obj = myCalendarCreate();
* bool param_1 = myCalendarBook(obj, start, end);
* myCalendarFree(obj);
*/
作者：xun-ge-v
链接：https://leetcode.cn/problems/my-calendar-i/solution/chun-cbu-yong-xian-duan-shu-yi-ge-si-lu-p0ic7/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。731.我的日程安排||
typedef struct {
int startCnt;//左边界下标
int endCnt;//右边界下标
int start[1000]; // 左边界
int end[1000]; // 右边界
} MyCalendarTwo;
//快排子函数,升序
int compare(const int *a, const int *b)
{
return a[0] > b[0] ? 1 : -1;
}
/*
*myCalendarThreeCreate：初始化MyCalendarThree * obj
返回值：初始化的结构体
*/
MyCalendarTwo* myCalendarTwoCreate() {
MyCalendarTwo * obj = (MyCalendarTwo *)malloc(sizeof(MyCalendarTwo));
memset(obj, 0, sizeof(MyCalendarTwo));
return obj;
}
bool myCalendarTwoBook(MyCalendarTwo* obj, int start, int end) {
// 插入新节点
obj->start[obj->startCnt++] = start;
obj->end[obj->endCnt++] = end;
// 左、右边界排序
qsort(obj->start, obj->startCnt, sizeof(obj->start[0]), compare);
qsort(obj->end, obj->endCnt, sizeof(obj->end[0]), compare);
int i = 0;
int j = 0;
int tmp = 0;
while (i < obj->startCnt && j < obj->endCnt) {
if(obj->start[i] == -1)//删除元素的位置，不再考虑
{
i++;
j++;
continue;
}
if (obj->start[i] < obj->end[j]) {//条件冲突数
tmp++;
i++;
} else {
tmp--;
j++;
}
int mmm = 1;
if(tmp == 3)
{
for(int m = 0; m < obj->startCnt; m++)//将原来加入的start删除
{
if(obj->start[m] == start)
{
obj->start[m] = -1;
break;
}
}
for(int m = 0; m < obj->startCnt; m++)//将原来加入的end删除
{
if(obj->end[m] == end)
{
obj->end[m] = -1;
break;
}
}
return false;
}
}
return true;
}
void myCalendarTwoFree(MyCalendarTwo* obj) {
free(obj);
}
/**
* Your MyCalendarTwo struct will be instantiated and called as such:
* MyCalendarTwo* obj = myCalendarTwoCreate();
* bool param_1 = myCalendarTwoBook(obj, start, end);
* myCalendarTwoFree(obj);
*/
作者：xun-ge-v
链接：https://leetcode.cn/problems/my-calendar-ii/solution/chun-c-by-xun-ge-v-3jh0/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。732.我的日程安排|||
typedef struct {
int startCnt;
int endCnt;
int start[400]; // 左边界
int end[400]; // 右边界
} MyCalendarThree;
int compare(const int *a, const int *b)
{
return a[0] > b[0] ? 1 : -1;
}
MyCalendarThree* myCalendarThreeCreate()
{
MyCalendarThree * obj = (MyCalendarThree *)malloc(sizeof(MyCalendarThree));
memset(obj, 0, sizeof(MyCalendarThree));
return obj;
}
int myCalendarThreeBook(MyCalendarThree* obj, int start, int end)
{
// 插入新节点
obj->start[obj->startCnt++] = start;
obj->end[obj->endCnt++] = end;
// 左、右边界排序
qsort(obj->start, obj->startCnt, sizeof(obj->start[0]), compare);
qsort(obj->end, obj->endCnt, sizeof(obj->end[0]), compare);
int i = 0;
int j = 0;
int tmp = 0;
int sum = 0;
while (i < obj->startCnt && j < obj->endCnt) {
if (obj->start[i] < obj->end[j]) {
tmp++;
sum = fmax(sum, tmp);
i++;
} else {
tmp--;
j++;
}
}
return sum;
}
void myCalendarThreeFree(MyCalendarThree* obj) {
if (obj != NULL) {
free(obj);
obj = NULL;
}
}
/**
* Your MyCalendarThree struct will be instantiated and called as such:
* MyCalendarThree* obj = myCalendarThreeCreate();
* int param_1 = myCalendarThreeBook(obj, start, end);
* myCalendarThreeFree(obj);
*/
作者：xun-ge-v
链接：https://leetcode.cn/problems/my-calendar-iii/solution/by-xun-ge-v-6isk/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。