729. My Calendar I

class MyCalendar {
    TreeMap<Integer, Integer> intervals;

    public MyCalendar() {
        intervals = new TreeMap<>();
    }

    public boolean book(int start, int end) {
        Integer prev = intervals.floorKey(start), next = intervals.ceilingKey(start);
        if ((prev == null || intervals.get(prev) <= start) && (next == null || next >= end)) {
            intervals.put(start, end);
            return true;
        }
        return false;
    }
}

找比要插入interval start小的start中最大的, 如果它对应的end比我们的start小, 我们的start不会和之前的interval有交叉. 然后找比当前start大的start中最小的. 如果它比我们的end大, 也不会有交叉.

需要记得的是map中的intervals都是不互相交叉的.

时间复杂度: O(nlogn)
空间复杂度: O(n)