LeetCode 731. My schedule II

731. My schedule II

 

【 Interval splitting and merging 】 I think it's complicated , Split the double overlapping interval , If you want to split an interval, you should consider the same endpoint .

class MyCalendarTwo {

    //  Splitting and merging of double ordered sets  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  Overlap is ：max(key, start) min(value, end)
                //  Left is  min(key, start) max(key, start)  On the right is  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);
 */

 【 Optimize 】 In fact, it doesn't matter if the primary interval overlaps with the secondary interval , Because first of all, we will go to the double interval judgment .

class MyCalendarTwo {

    //  double 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);
 */