LeetCode 729. My schedule I

729. My schedule I

 

【 Ordered set 】 First, the range of the interval reaches 10^9, So it can't pass start + 1,end - 1 This kind of difference group indicates whether it has been covered . And because this is online inquiry （ Queries are dynamic , Not all intervals are inserted before querying ） Because it cannot be discretized . So consider TreeMap Carry out dynamic insertion and judgment of intervals .

Sort by left endpoint , For New Area , lookup <end（ Be careful ： here end It's open , So look for < He ） Maximum key, Judge value whether >start, If > Explain that the interval coincides , Otherwise, insert it .

distinguish ：java in TreeMap Yes ：floorKey(floorEntry),lowerKey(lowerEntry) The two methods , The difference is that the former contains equal to . Empathy ceilKey(highterKey) It's also .

class MyCalendar {

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