# 0731. My Calendar II
###### tags: `Leetcode` `Medium` `Design` `TreeMap` `Line Sweep`
## 思路
### $O(NlogN)$ each book() call
把所有和```[start, end)```重合的interval都拿出来
然后看他们有没有重叠的 如果有的话就说明当下interval不能被加进去
### $O(N)$ each book() call
插入treemap的时间是$O(logN)$ 遍历所有timeslot的复杂度是$O(N)$
用treemap存 然后用差分法 这样就不用排序
## Code
### 思路一

class MyCalendarTwo {
    List<int[]> time;
    public MyCalendarTwo() {
        time = new ArrayList<>();
    }
    
    public boolean book(int start, int end) {
        List<int[]> temp = new ArrayList<>();
        for(int[] t:time){
            if(!(t[0]>=end || t[1]<=start)){
                temp.add(t);
            }
        }
        Collections.sort(temp, (a,b)->(a[0]==b[0]?a[1]-b[1]:a[0]-b[0]));
        for(int i=1; i<temp.size(); i++){
            if(temp.get(i)[0]<temp.get(i-1)[1]) return false;
        }
        time.add(new int[]{start, end});
        return true;
    }
}

### 思路二 TreeMap

class MyCalendarTwo {
    TreeMap<Integer, Integer> map;
    public MyCalendarTwo() {
        map = new TreeMap<>();
    }
    
    public boolean book(int start, int end) {
        map.put(start, map.getOrDefault(start, 0)+1);
        map.put(end, map.getOrDefault(end, 0)-1);
        int count = 0;
        for(Map.Entry<Integer, Integer> entry:map.entrySet()){
            count += entry.getValue();
            if(count>2){
                map.put(start, map.get(start)-1);
                map.put(end, map.get(end)+1);
                return false;
            }
        }
        return true;
    }
}