Sword finger offer II 058. schedule (medium design segment tree treemap ordered set)

The finger of the sword Offer II 058. calendar

Please implement a MyCalendar Class to store your schedule . If there is no other schedule for the time to be added , You can store this new schedule .

MyCalendar There is one book(int start, int end) Method . It means in start To end Add a schedule in time , Be careful , The time here is a half open interval , namely [start, end), The set of real Numbers x For the range of , start <= x < end.

When there is some time overlap between the two schedules （ For example, both schedules are in the same time ）, There will be repeat bookings .

Every time you call MyCalendar.book When the method is used , If the schedule can be successfully added to the calendar without causing duplicate bookings , return true. otherwise , return false And don't add the schedule to the calendar .

Please follow the steps below to call MyCalendar class : MyCalendar cal = new MyCalendar(); MyCalendar.book(start, end)

Example :

Input :
[“MyCalendar”,“book”,“book”,“book”]
[[],[10,20],[15,25],[20,30]]
Output : [null,true,false,true]
explain :
MyCalendar myCalendar = new MyCalendar();
MyCalendar.book(10, 20); // returns true
MyCalendar.book(15, 25); // returns false , The second schedule cannot be added to the calendar , Because of time 15 It has been scheduled by the first schedule
MyCalendar.book(20, 30); // returns true , The third schedule can be added to the calendar , Because the first schedule doesn't include time 20

Tips ：

Each test case , call MyCalendar.book The function is no more than 1000 Time .
0 <= start < end <= 109

source ： Power button （LeetCode）
link ：https://leetcode-cn.com/problems/fi9suh
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

analysis

utilize TreeMap Method to find the largest smaller than the current start Of key And the smallest is greater than the current start Of key Just judge .

Answer key （Java）

class MyCalendar {
    
    private TreeMap<Long, Long> map = new TreeMap<>();

    public MyCalendar() {
    

    }
    
    public boolean book(int start, int end) {
    
        Long lower = map.floorKey((long)start);
        Long higher = map.ceilingKey((long)start);
        if (lower != null && map.get(lower) > start || higher != null && higher < end) {
    
            return false;
        }
        map.put((long)start, (long)end);
        return true;
    }
}

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