题目描述

实现一个MyCalendarThree的类来进行事件管理。
这个类只有一个方法 book(int start, int end)
表示添加一个事件，这个事件从start开始，end事件结束（左闭右开）
问添加这个事件之后，有最多多少个事件是重叠的

样例

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

算法

(端点排序) $O(n^2)$

将一个区间拆分为两个端点，并且标记左端点还是右端点。
将这些端点存入一个数组中，记录两个值，一个是这个端点是否是左右端点，一个是这个端点的值。
并且在插入的过程中保持这个数组有序（插入排序）。

接下来维护一个当前区间的最大值
扫描整个数组，碰到左端点值加一，碰到右端点值减一（用纸笔画一下就明白了）。
最后返回最大值。

时间复杂度分析：一共n次插入，每次插入两个元素，并且维持这个数组有序，并且每次都要扫描这个数组。
n次操作，每次操作都需要 $O(n)$的复杂度。一共是 $O(n^2)$的复杂度

C++ 代码

struct node{
    int value;
    bool isleft;
};

bool cmp(node l,node r){
    if (l.value == r.value )
        return l.isleft?true:false;
    return l.value < r. value;
}
class MyCalendarThree {
public:
    vector<node> res;
    MyCalendarThree() {
        res.resize(0);
    }

    int book(int start, int end) {
        node cur1;
        node cur2;

        cur1.isleft = true; cur1.value = start;

        cur2.isleft = false;cur2.value = end-1;
        int sz = res.size();
        for (int i = 0;i<res.size();++i){
            if (cmp(cur1,res[i])){
                res.insert(res.begin()+i,cur1);
                break;
            }
        }
        if (res.size() != sz+1)
            res.push_back(cur1);
        sz = res.size();
        for (int i = 0;i<res.size();++i){
            if (cmp(cur2,res[i])){
                res.insert(res.begin()+i,cur2);
                break;
            }
        }
        if (res.size()!= sz+1)
            res.push_back(cur2);


        int cnt = 0;
        int maxres = 0;
        for (int i = 0;i<res.size();++i){
            if (res[i].isleft) {
                cnt++;
                maxres = max(maxres,cnt);
            }
            else
                cnt--;
        }


        return maxres;


    }
};

/**
 * Your MyCalendarThree object will be instantiated and called as such:
 * MyCalendarThree obj = new MyCalendarThree();
 * int param_1 = obj.book(start,end);
 */