# 731 My Calendar II

實作一個class叫MyCalendarTwo來存events。當不會造成triple booking時就可以加入新event。 題目提供class 框架：

class MyCalendarTwo {
    public MyCalendarTwo() {        
    }

    public boolean book(int start, int end) {  
    }
}

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

Idea 把有overlap的區間存在一個data structure， 把沒有overlap的區間存在另一個data structure。 每book新的區間，和overlap比對，若有重疊，return false， 不然就return true，並加入nooverlap

Pseudocode

class MyCalendarTwo {
    List<start/end pair> overlap
    List<start/end pair> nooverlap
    public MyCalendarTwo() {
        initialize overlap and nooverlap
    }

    public boolean book(int start, int end) {
        for all pairs in overlap
            if start > pair.end || end < pair.start
                continue
            else // there is overlap
                return false

        for all pairs in nooverlap
            if start > pair.end || end < pair.start
                continue
            else
                merge and add to overlap

        add start/end pair to nooverlap
        return true        
    }
}

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

Code

class MyCalendarTwo {
    List<List<Integer>> overlap;
    List<List<Integer>> nooverlap;

    public MyCalendarTwo() {
        overlap = new ArrayList<>();
        nooverlap = new ArrayList<>();
    }

    public boolean book(int start, int end) {
        for(List<Integer> list : overlap){
            if(start >= list.get(1) || end <= list.get(0))  continue;
            else return false;
        }

        for(List<Integer> list : nooverlap){
            if(start >= list.get(1) || end <= list.get(0))  continue;
            else{
                overlap.add(new ArrayList<>(Arrays.asList(Math.max(start, list.get(0)), Math.min(end, list.get(1)))));
            }
        }

        nooverlap.add(new ArrayList<>(Arrays.asList(start, end)));
        return true;
    }
}

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