Sword finger offer II 058: schedule

subject

Topic linking
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 

Problem solving

Method 1 ：map+ Two points search

because map Will automatically key Sort , So sort the left boundary directly .
Find... By bisection , Find greater than or equal to end, The left border .
Just make , The right boundary ratio of the previous one start Small can be inserted successfully

class MyCalendar {
    
public:
    map<int,int> mp;
    MyCalendar() {
    

    }
    bool book(int start, int end) {
    
        map<int,int>::iterator it=mp.lower_bound(end);//  return  key value   Greater than or equal to  end  The first position 
        if(it==mp.begin()||(--it)->second<=start){
    
            mp[start]=end;
            return true;
        }
        return false;
    }
};