题目描述

we have set of intervals added before iterations,
given an interval for query, we need to check whether the given interval has conflict with the current set of interval. If not we will add the interval, otherwise we will skip the interval.

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

class MyCalendar {
public:
    map<int,int> hash; 
    MyCalendar() {

    }

    bool book(int start, int end) {
        if(hash.size()==0){
            hash[start] = end; 
            return true; 
        }
        auto it = hash.lower_bound(start); 
        bool flag = false; 
        if(it == hash.begin()&&end<=it->first){
            flag = true; 
        }else if(it==hash.end()&&(--it)->second<=start){
            flag = true; 
        }else{
            auto pre = it ;
            pre--; 
            if(pre->second<=start&&end<=it->first){
                flag = true; 
            }
        }
        if(flag){
            hash[start] = end; 
            return true; 
        }
        return false; 
    }
};

/**
 * Your MyCalendar object will be instantiated and called as such:
 * MyCalendar* obj = new MyCalendar();
 * bool param_1 = obj->book(start,end);
 */