LeetCode 729. 我的日程安排表 I

729. 我的日程安排表 I

 

【有序集合】先看区间的范围达到10^9，因此不能通过start + 1，end - 1这种的差分数组来表示是否已经被覆盖。又因为这是在线查询（查询是动态的，并不是所有区间都插入才查询）因为无法进行离散化。所以考虑TreeMap进行区间的动态插入和判断。

按照左端点排序，对于新区间，查找<end（注意：这里end是开的，所以要查找<他）的最大key，判断value是否>start，如果>说明区间重合，否则插入即可。

区分：java中TreeMap有：floorKey(floorEntry)，lowerKey(lowerEntry)两种方法，区别在于前者包含等于。同理ceilKey(highterKey)也是。

class MyCalendar {

    // 有序集合 1:24 1:26

    TreeMap<Integer, Integer> map = new TreeMap();

    public MyCalendar() {

    }
    
    public boolean book(int start, int end) {
        Integer key = map.lowerKey(end);
        if (key != null) {
            if (map.get(key) > start) {
                return false;
            }
        }
        map.put(start, end);
        return true;
    }
}

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