LeetCode 731. 我的日程安排表 II

731. 我的日程安排表 II

 

【区间拆分与合并】想复杂了，把双次重叠区间给拆分开了，如果进行区间拆分的话要考虑端点相同的情况。

class MyCalendarTwo {

    // 双有序集合拆分与合并 1:27 2:47

    TreeMap<Integer, Integer> m1 = new TreeMap();
    TreeMap<Integer, Integer> m2 = new TreeMap();

    public MyCalendarTwo() {

    }
    
    public boolean book(int start, int end) {
        Integer k2 = m2.lowerKey(end);
        if (k2 != null) {
            if (m2.get(k2) > start) {
                return false;
            }
        }
        Integer key = m1.lowerKey(end);
        if (key == null) {
            m1.put(start, end);
            return true;
        }
        int value = m1.get(key);
        if (value <= start) {
            m1.put(start, end);
            return true;
        }
        while (key != null) {
            if (m1.get(key) > start) {
                value = m1.get(key);
                // key  start value end 重叠是：max(key, start) min(value, end)
                // 左是 min(key, start) max(key, start) 右是 min(value, end) max(value, end)
                int l1 = Math.min(key, start);
                int e1 = Math.max(key, start);
                int l2 = Math.min(value, end);
                int e2 = Math.max(value, end);
                m2.put(e1, l2);
                m1.remove(key);
                if (l2 != e2) {
                    m1.put(l2, e2);
                }
                if (l1 != e1) {
                    start = l1;
                    end = e1;
                    key = m1.lowerKey(end);
                    if (key == null) {
                        m1.put(start, end);
                        return true;
                    }
                } else {
                    break;
                }
            } else {
                m1.put(start, end);
                break;
            }
        }
        return true;
    }
}

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

 【优化】其实一重区间和二重区间有重叠也是没关系的，因为首先就会去二重区间判断。

class MyCalendarTwo {

    // 双TreeMap 2:55

    TreeMap<Integer, Integer> m1 = new TreeMap();
    TreeMap<Integer, Integer> m2 = new TreeMap();

    public MyCalendarTwo() {

    }
    
    public boolean book(int start, int end) {
        Integer k2 = m2.lowerKey(end);
        if (k2 != null && m2.get(k2) > start) {
            return false;
        }
        Integer key = m1.lowerKey(end);
        while (key != null) {
            int value = m1.get(key);
            if (value <= start) {
                break;
            }
            m1.remove(key);
            m2.put(Math.max(start, key), Math.min(end, value));
            start = Math.min(start, key);
            end = Math.max(end, value);
            key = m1.lowerKey(end);
        }
        m1.put(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);
 */