You are implementing a program to use as your calendar. We can add a new event if adding the event will not cause a double booking.
A double booking happens when two events have some non-empty intersection (i.e., some moment is common to both events.).
The event can be represented as a pair of integers startTime and endTime that represents a booking on the half-open interval [startTime, endTime), the range of real numbers x such that startTime <= x < endTime.
Implement the MyCalendar class:
MyCalendar() Initializes the calendar object.
boolean book(int startTime, int endTime) Returns true if the event can be added to the calendar successfully without causing a double booking. Otherwise, return false and do not add the event to the calendar.
Example 1:
Input
["MyCalendar", "book", "book", "book"]
[[], [10, 20], [15, 25], [20, 30]]
Output
[null, true, false, true]
Explanation
MyCalendar myCalendar = new MyCalendar();
myCalendar.book(10, 20); // return True
myCalendar.book(15, 25); // return False, It can not be booked because time 15 is already booked by another event.
myCalendar.book(20, 30); // return True, The event can be booked, as the first event takes every time less than 20, but not including 20.
Constraints:
0 <= start < end <= 109
At most 1000 calls will be made to book.
Solutions
Solution 1
1 2 3 4 5 6 7 8 9101112131415161718
fromsortedcontainersimportSortedDictclassMyCalendar:def__init__(self):self.sd=SortedDict()defbook(self,start:int,end:int)->bool:idx=self.sd.bisect_right(start)ifidx<len(self.sd)andend>self.sd.values()[idx]:returnFalseself.sd[end]=startreturnTrue# Your MyCalendar object will be instantiated and called as such:# obj = MyCalendar()# param_1 = obj.book(start,end)
importjava.util.Map;importjava.util.TreeMap;classMyCalendar{privatefinalTreeMap<Integer,Integer>tm=newTreeMap<>();publicMyCalendar(){}publicbooleanbook(intstart,intend){Map.Entry<Integer,Integer>ent=tm.floorEntry(start);if(ent!=null&&ent.getValue()>start){returnfalse;}ent=tm.ceilingEntry(start);if(ent!=null&&ent.getKey()<end){returnfalse;}tm.put(start,end);returntrue;}}/** * Your MyCalendar object will be instantiated and called as such: MyCalendar * obj = new MyCalendar(); boolean param_1 = obj.book(start,end); */
classMyCalendar{public:map<int,int>m;MyCalendar(){}boolbook(intstart,intend){++m[start];--m[end];ints=0;for(auto&[k,v]:m){s+=v;if(s>1){--m[start];++m[end];returnfalse;}}returntrue;}};/** * Your MyCalendar object will be instantiated and called as such: * MyCalendar* obj = new MyCalendar(); * bool param_1 = obj->book(start,end); */
typeMyCalendarstruct{rbt*redblacktree.Tree}funcConstructor()MyCalendar{returnMyCalendar{rbt:redblacktree.NewWithIntComparator(),}}func(this*MyCalendar)Book(startint,endint)bool{ifp,ok:=this.rbt.Floor(start);ok&&p.Value.(int)>start{returnfalse}ifp,ok:=this.rbt.Ceiling(start);ok&&p.Key.(int)<end{returnfalse}this.rbt.Put(start,end)returntrue}/** * Your MyCalendar object will be instantiated and called as such: * obj := Constructor(); * param_1 := obj.Book(start,end); */
1 2 3 4 5 6 7 8 9101112131415161718192021222324
classMyCalendar{privatecalendar:number[][];constructor(){this.calendar=[];}book(start:number,end:number):boolean{for(constitemofthis.calendar){if(end<=item[0]||item[1]<=start){continue;}returnfalse;}this.calendar.push([start,end]);returntrue;}}/** * Your MyCalendar object will be instantiated and called as such: * var obj = new MyCalendar() * var param_1 = obj.book(start,end) */
usestd::collections::BTreeMap;structMyCalendar{bt:BTreeMap<i32,i32>,}/** * `&self` means the method takes an immutable reference. * If you need a mutable reference, change it to `&mut self` instead. */implMyCalendar{fnnew()->Self{MyCalendar{bt:BTreeMap::new(),}}fnbook(&mutself,start:i32,end:i32)->bool{ifletSome((_,&val))=self.bt.range(..=start).last(){println!("{} {} {}",start,end,val);ifval>start{returnfalse;}}ifletSome((&key,_))=self.bt.range(start..).next(){ifkey<end{returnfalse;}}self.bt.insert(start,end);true}}
1 2 3 4 5 6 7 8 910111213141516171819202122232425
varMyCalendar=function(){this.calendar=[];};/** * @param {number} start * @param {number} end * @return {boolean} */MyCalendar.prototype.book=function(start,end){for(constitemofthis.calendar){if(end<=item[0]||item[1]<=start){continue;}returnfalse;}this.calendar.push([start,end]);returntrue;};/** * Your MyCalendar object will be instantiated and called as such: * var obj = new MyCalendar() * var param_1 = obj.book(start,end) */