You are implementing a program to use as your calendar. We can add a new event if adding the event will not cause a triple booking.
A triple booking happens when three events have some non-empty intersection (i.e., some moment is common to all the three 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 MyCalendarTwo class:
MyCalendarTwo() 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 triple booking. Otherwise, return false and do not add the event to the calendar.
Example 1:
Input
["MyCalendarTwo", "book", "book", "book", "book", "book", "book"]
[[], [10, 20], [50, 60], [10, 40], [5, 15], [5, 10], [25, 55]]
Output
[null, true, true, true, false, true, true]
Explanation
MyCalendarTwo myCalendarTwo = new MyCalendarTwo();
myCalendarTwo.book(10, 20); // return True, The event can be booked.
myCalendarTwo.book(50, 60); // return True, The event can be booked.
myCalendarTwo.book(10, 40); // return True, The event can be double booked.
myCalendarTwo.book(5, 15); // return False, The event cannot be booked, because it would result in a triple booking.
myCalendarTwo.book(5, 10); // return True, The event can be booked, as it does not use time 10 which is already double booked.
myCalendarTwo.book(25, 55); // return True, The event can be booked, as the time in [25, 40) will be double booked with the third event, the time [40, 50) will be single booked, and the time [50, 55) will be double booked with the second event.
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 91011121314151617181920212223
fromsortedcontainersimportSortedDictclassMyCalendarTwo:def__init__(self):self.sd=SortedDict()defbook(self,start:int,end:int)->bool:self.sd[start]=self.sd.get(start,0)+1self.sd[end]=self.sd.get(end,0)-1s=0forvinself.sd.values():s+=vifs>2:self.sd[start]-=1self.sd[end]+=1returnFalsereturnTrue# Your MyCalendarTwo object will be instantiated and called as such:# obj = MyCalendarTwo()# param_1 = obj.book(start,end)
classMyCalendarTwo{privateMap<Integer,Integer>tm=newTreeMap<>();publicMyCalendarTwo(){}publicbooleanbook(intstart,intend){tm.put(start,tm.getOrDefault(start,0)+1);tm.put(end,tm.getOrDefault(end,0)-1);ints=0;for(intv:tm.values()){s+=v;if(s>2){tm.put(start,tm.get(start)-1);tm.put(end,tm.get(end)+1);returnfalse;}}returntrue;}}/** * Your MyCalendarTwo object will be instantiated and called as such: * MyCalendarTwo obj = new MyCalendarTwo(); * boolean param_1 = obj.book(start,end); */
classMyCalendarTwo{public:map<int,int>m;MyCalendarTwo(){}boolbook(intstart,intend){++m[start];--m[end];ints=0;for(auto&[_,v]:m){s+=v;if(s>2){--m[start];++m[end];returnfalse;}}returntrue;}};/** * Your MyCalendarTwo object will be instantiated and called as such: * MyCalendarTwo* obj = new MyCalendarTwo(); * bool param_1 = obj->book(start,end); */
typeMyCalendarTwostruct{*redblacktree.Tree}funcConstructor()MyCalendarTwo{returnMyCalendarTwo{redblacktree.NewWithIntComparator()}}func(this*MyCalendarTwo)Book(startint,endint)bool{add:=func(key,valint){ifv,ok:=this.Get(key);ok{this.Put(key,v.(int)+val)}else{this.Put(key,val)}}add(start,1)add(end,-1)s:=0it:=this.Iterator()forit.Next(){s+=it.Value().(int)ifs>2{add(start,-1)add(end,1)returnfalse}}returntrue}/** * Your MyCalendarTwo object will be instantiated and called as such: * obj := Constructor(); * param_1 := obj.Book(start,end); */
classMyCalendarTwo{privateevents:[number,number][];privateoverlaps:[number,number][];constructor(){this.events=[];this.overlaps=[];}book(start:number,end:number):boolean{for(const[s,e]ofthis.overlaps){if(Math.max(start,s)<Math.min(end,e)){returnfalse;}}for(const[s,e]ofthis.events){if(Math.max(start,s)<Math.min(end,e)){this.overlaps.push([Math.max(start,s),Math.min(end,e)]);}}this.events.push([start,end]);returntrue;}}/** * Your MyCalendarTwo object will be instantiated and called as such: * var obj = new MyCalendarTwo() * var param_1 = obj.book(start,end) */
varMyCalendarTwo=function(){this.events=[];this.overlaps=[];};/** * @param {number} start * @param {number} end * @return {boolean} */MyCalendarTwo.prototype.book=function(start,end){for(let[s,e]ofthis.overlaps){if(Math.max(start,s)<Math.min(end,e)){returnfalse;}}for(let[s,e]ofthis.events){if(Math.max(start,s)<Math.min(end,e)){this.overlaps.push([Math.max(start,s),Math.min(end,e)]);}}this.events.push([start,end]);returntrue;};/** * Your MyCalendarTwo object will be instantiated and called as such: * var obj = new MyCalendarTwo() * var param_1 = obj.book(start,end) */
classNode:def__init__(self,l,r):self.left=Noneself.right=Noneself.l=lself.r=rself.mid=(l+r)>>1self.v=0self.add=0classSegmentTree:def__init__(self):self.root=Node(1,int(1e9+1))defmodify(self,l,r,v,node=None):ifl>r:returnifnodeisNone:node=self.rootifnode.l>=landnode.r<=r:node.v+=vnode.add+=vreturnself.pushdown(node)ifl<=node.mid:self.modify(l,r,v,node.left)ifr>node.mid:self.modify(l,r,v,node.right)self.pushup(node)defquery(self,l,r,node=None):ifl>r:return0ifnodeisNone:node=self.rootifnode.l>=landnode.r<=r:returnnode.vself.pushdown(node)v=0ifl<=node.mid:v=max(v,self.query(l,r,node.left))ifr>node.mid:v=max(v,self.query(l,r,node.right))returnvdefpushup(self,node):node.v=max(node.left.v,node.right.v)defpushdown(self,node):ifnode.leftisNone:node.left=Node(node.l,node.mid)ifnode.rightisNone:node.right=Node(node.mid+1,node.r)ifnode.add:node.left.v+=node.addnode.right.v+=node.addnode.left.add+=node.addnode.right.add+=node.addnode.add=0classMyCalendarTwo:def__init__(self):self.tree=SegmentTree()defbook(self,start:int,end:int)->bool:ifself.tree.query(start+1,end)>=2:returnFalseself.tree.modify(start+1,end,1)returnTrue# Your MyCalendarTwo object will be instantiated and called as such:# obj = MyCalendarTwo()# param_1 = obj.book(start,end)
classNode{Nodeleft;Noderight;intl;intr;intmid;intv;intadd;publicNode(intl,intr){this.l=l;this.r=r;this.mid=(l+r)>>1;}}classSegmentTree{privateNoderoot=newNode(1,(int)1e9+1);publicSegmentTree(){}publicvoidmodify(intl,intr,intv){modify(l,r,v,root);}publicvoidmodify(intl,intr,intv,Nodenode){if(l>r){return;}if(node.l>=l&&node.r<=r){node.v+=v;node.add+=v;return;}pushdown(node);if(l<=node.mid){modify(l,r,v,node.left);}if(r>node.mid){modify(l,r,v,node.right);}pushup(node);}publicintquery(intl,intr){returnquery(l,r,root);}publicintquery(intl,intr,Nodenode){if(l>r){return0;}if(node.l>=l&&node.r<=r){returnnode.v;}pushdown(node);intv=0;if(l<=node.mid){v=Math.max(v,query(l,r,node.left));}if(r>node.mid){v=Math.max(v,query(l,r,node.right));}returnv;}publicvoidpushup(Nodenode){node.v=Math.max(node.left.v,node.right.v);}publicvoidpushdown(Nodenode){if(node.left==null){node.left=newNode(node.l,node.mid);}if(node.right==null){node.right=newNode(node.mid+1,node.r);}if(node.add!=0){Nodeleft=node.left,right=node.right;left.add+=node.add;right.add+=node.add;left.v+=node.add;right.v+=node.add;node.add=0;}}}classMyCalendarTwo{privateSegmentTreetree=newSegmentTree();publicMyCalendarTwo(){}publicbooleanbook(intstart,intend){if(tree.query(start+1,end)>=2){returnfalse;}tree.modify(start+1,end,1);returntrue;}}/** * Your MyCalendarTwo object will be instantiated and called as such: * MyCalendarTwo obj = new MyCalendarTwo(); * boolean param_1 = obj.book(start,end); */
classNode{public:Node*left;Node*right;intl;intr;intmid;intv;intadd;Node(intl,intr){this->l=l;this->r=r;this->mid=(l+r)>>1;this->left=this->right=nullptr;v=add=0;}};classSegmentTree{private:Node*root;public:SegmentTree(){root=newNode(1,1e9+1);}voidmodify(intl,intr,intv){modify(l,r,v,root);}voidmodify(intl,intr,intv,Node*node){if(l>r)return;if(node->l>=l&&node->r<=r){node->v+=v;node->add+=v;return;}pushdown(node);if(l<=node->mid)modify(l,r,v,node->left);if(r>node->mid)modify(l,r,v,node->right);pushup(node);}intquery(intl,intr){returnquery(l,r,root);}intquery(intl,intr,Node*node){if(l>r)return0;if(node->l>=l&&node->r<=r)returnnode->v;pushdown(node);intv=0;if(l<=node->mid)v=max(v,query(l,r,node->left));if(r>node->mid)v=max(v,query(l,r,node->right));returnv;}voidpushup(Node*node){node->v=max(node->left->v,node->right->v);}voidpushdown(Node*node){if(!node->left)node->left=newNode(node->l,node->mid);if(!node->right)node->right=newNode(node->mid+1,node->r);if(node->add){Node*left=node->left;Node*right=node->right;left->v+=node->add;right->v+=node->add;left->add+=node->add;right->add+=node->add;node->add=0;}}};classMyCalendarTwo{public:SegmentTree*tree=newSegmentTree();MyCalendarTwo(){}boolbook(intstart,intend){if(tree->query(start+1,end)>=2)returnfalse;tree->modify(start+1,end,1);returntrue;}};/** * Your MyCalendarTwo object will be instantiated and called as such: * MyCalendarTwo* obj = new MyCalendarTwo(); * bool param_1 = obj->book(start,end); */
typenodestruct{left*noderight*nodel,mid,rintv,addint}funcnewNode(l,rint)*node{return&node{l:l,r:r,mid:int(uint(l+r)>>1),}}typesegmentTreestruct{root*node}funcnewSegmentTree()*segmentTree{return&segmentTree{root:newNode(1,1e9+1),}}func(t*segmentTree)modify(l,r,vint,n*node){ifl>r{return}ifn.l>=l&&n.r<=r{n.v+=vn.add+=vreturn}t.pushdown(n)ifl<=n.mid{t.modify(l,r,v,n.left)}ifr>n.mid{t.modify(l,r,v,n.right)}t.pushup(n)}func(t*segmentTree)query(l,rint,n*node)int{ifl>r{return0}ifn.l>=l&&n.r<=r{returnn.v}t.pushdown(n)v:=0ifl<=n.mid{v=max(v,t.query(l,r,n.left))}ifr>n.mid{v=max(v,t.query(l,r,n.right))}returnv}func(t*segmentTree)pushup(n*node){n.v=max(n.left.v,n.right.v)}func(t*segmentTree)pushdown(n*node){ifn.left==nil{n.left=newNode(n.l,n.mid)}ifn.right==nil{n.right=newNode(n.mid+1,n.r)}ifn.add!=0{n.left.add+=n.addn.right.add+=n.addn.left.v+=n.addn.right.v+=n.addn.add=0}}typeMyCalendarTwostruct{tree*segmentTree}funcConstructor()MyCalendarTwo{returnMyCalendarTwo{newSegmentTree()}}func(this*MyCalendarTwo)Book(startint,endint)bool{ifthis.tree.query(start+1,end,this.tree.root)>=2{returnfalse}this.tree.modify(start+1,end,1,this.tree.root)returntrue}/** * Your MyCalendarTwo object will be instantiated and called as such: * obj := Constructor(); * param_1 := obj.Book(start,end); */