题目

实现一个 MyCalendar 类来存放你的日程安排。如果要添加的日程安排不会造成 重复预订 ，则可以存储这个新的日程安排。

当两个日程安排有一些时间上的交叉时（例如两个日程安排都在同一时间内），就会产生 重复预订 。

日程可以用一对整数 start 和 end 表示，这里的时间是半开区间，即 [start, end), 实数 x 的范围为，  start <= x < end 。

实现 MyCalendar 类：

MyCalendar() 初始化日历对象。
boolean book(int start, int end) 如果可以将日程安排成功添加到日历中而不会导致重复预订，返回 true 。否则，返回 false 并且不要将该日程安排添加到日历中。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/my-calendar-i
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

示例

思路

线段树要解决的问题是: 在一个实时更新的动态数组中查询区间和(或广义的区间状态,如区间积,区间最大最小值).

若所查询的数组为静态数组,则此问题只需要使用数组前缀和即能解决.

本题需要对数组进行查询与存入可以使用线段树，但是对于线段树不熟悉的也可以用数组替换线段树

定义两个数组空间，分别保存左区间节点和右区间，进一步优化设置两个变量，保存左区间最小值和右区间最大值，当区间左节点大于最大值或者区间右节点小于最小值时，区间肯定不会在数组空间中重复，所以存入数组空间并更新最大最小值

当区间左右节点在最值里面时，遍历数组空间，寻找区间是否与其他空间有重合地方，没有存入，有就退出，不需要更新最值，因为是在最值里面的

存入一个数据就对数组空间进行升序处理，保证数组空间的连续性

代码

typedef struct {
    int * startNums;
    int * endNums;
    int min;
    int max;
    int inode;
} MyCalendar;
 
 
MyCalendar* myCalendarCreate() {
    MyCalendar * obj = malloc(sizeof(MyCalendar) * 1);
    obj->startNums = malloc(sizeof(int) * 1000);
    obj->endNums = malloc(sizeof(int) * 1000);
    obj->min = INT_MAX;
    obj->max = INT_MIN;
    obj->inode = 0;
    return obj;
}
#define MAX(a , b) ((a) > (b) ? (a) : (b))
#define MIX(a , b) ((a) < (b) ? (a) : (b))
int cmp(const void * a, const void * b)
{
    return *(int *)a - *(int *)b;
}
bool myCalendarBook(MyCalendar* obj, int start, int end) {
    if(start >= obj->max || end <= obj->min)//第一种情况，区间边界大于或者小于最值
    {
        obj->max = MAX(obj->max , end);
        obj->min = MIX(obj->min , start);
        obj->startNums[obj->inode] = start;
        obj->endNums[obj->inode] = end;
        obj->inode++;
        qsort(obj->startNums, obj->inode, sizeof(obj->startNums[0]), cmp);
        qsort(obj->endNums, obj->inode, sizeof(obj->endNums[0]), cmp);
        return true;
    }
    for(int i = 0; i < obj->inode-1; i++)//第二种情况，遍历区间数组，寻找能否存入
    {
        if(start >= obj->endNums[i])
        {
            if(end <= obj->startNums[i+1])
            {
                obj->startNums[obj->inode] = start;
                obj->endNums[obj->inode] = end;
                obj->inode++;
                qsort(obj->startNums, obj->inode, sizeof(obj->startNums[0]), cmp);
                qsort(obj->endNums, obj->inode, sizeof(obj->endNums[0]), cmp);
                return true;
            }
        }
        else
        {
            return false;
        }
    }
    return false;
}
 
void myCalendarFree(MyCalendar* obj) {
    free(obj->startNums);
    free(obj->endNums);
    free(obj);
}
 
/**
 * Your MyCalendar struct will be instantiated and called as such:
 * MyCalendar* obj = myCalendarCreate();
 * bool param_1 = myCalendarBook(obj, start, end);
 
 * myCalendarFree(obj);
*/

时间空间复杂度