A k-booking happens when k events have some non-empty intersection (i.e., there is some time that is common to all k events.)
You are given some events [startTime, endTime), after each given event, return an integer k representing the maximum k-booking between all the previous events.
Implement the MyCalendarThree class:
MyCalendarThree() Initializes the object.
int book(int startTime, int endTime) Returns an integer k representing the largest integer such that there exists a k-booking in the calendar.
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=0classMyCalendarThree:def__init__(self):self.tree=SegmentTree()defbook(self,start:int,end:int)->int:self.tree.modify(start+1,end,1)returnself.tree.query(1,int(1e9+1))# Your MyCalendarThree object will be instantiated and called as such:# obj = MyCalendarThree()# 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;}}}classMyCalendarThree{privateSegmentTreetree=newSegmentTree();publicMyCalendarThree(){}publicintbook(intstart,intend){tree.modify(start+1,end,1);returntree.query(1,(int)1e9+1);}}/** * Your MyCalendarThree object will be instantiated and called as such: * MyCalendarThree obj = new MyCalendarThree(); * int 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;}}};classMyCalendarThree{public:SegmentTree*tree;MyCalendarThree(){tree=newSegmentTree();}intbook(intstart,intend){tree->modify(start+1,end,1);returntree->query(1,1e9+1);}};/** * Your MyCalendarThree object will be instantiated and called as such: * MyCalendarThree* obj = new MyCalendarThree(); * int 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}}typeMyCalendarThreestruct{tree*segmentTree}funcConstructor()MyCalendarThree{returnMyCalendarThree{newSegmentTree()}}func(this*MyCalendarThree)Book(startint,endint)int{this.tree.modify(start+1,end,1,this.tree.root)returnthis.tree.query(1,int(1e9)+1,this.tree.root)}/** * Your MyCalendarThree object will be instantiated and called as such: * obj := Constructor(); * param_1 := obj.Book(start,end); */