A concert hall has n rows numbered from 0 to n - 1, each with m seats, numbered from 0 to m - 1. You need to design a ticketing system that can allocate seats in the following cases:
If a group of k spectators can sit together in a row.
If every member of a group of k spectators can get a seat. They may or may not sit together.
Note that the spectators are very picky. Hence:
They will book seats only if each member of their group can get a seat with row number less than or equal to maxRow. maxRow can vary from group to group.
In case there are multiple rows to choose from, the row with the smallest number is chosen. If there are multiple seats to choose in the same row, the seat with the smallest number is chosen.
Implement the BookMyShow class:
BookMyShow(int n, int m) Initializes the object with n as number of rows and m as number of seats per row.
int[] gather(int k, int maxRow) Returns an array of length 2 denoting the row and seat number (respectively) of the first seat being allocated to the k members of the group, who must sit together. In other words, it returns the smallest possible r and c such that all [c, c + k - 1] seats are valid and empty in row r, and r <= maxRow. Returns [] in case it is not possible to allocate seats to the group.
boolean scatter(int k, int maxRow) Returns true if all k members of the group can be allocated seats in rows 0 to maxRow, who may or may not sit together. If the seats can be allocated, it allocates k seats to the group with the smallest row numbers, and the smallest possible seat numbers in each row. Otherwise, returns false.
Example 1:
Input
["BookMyShow", "gather", "gather", "scatter", "scatter"]
[[2, 5], [4, 0], [2, 0], [5, 1], [5, 1]]
Output
[null, [0, 0], [], true, false]
Explanation
BookMyShow bms = new BookMyShow(2, 5); // There are 2 rows with 5 seats each
bms.gather(4, 0); // return [0, 0]
// The group books seats [0, 3] of row 0.
bms.gather(2, 0); // return []
// There is only 1 seat left in row 0,
// so it is not possible to book 2 consecutive seats.
bms.scatter(5, 1); // return True
// The group books seat 4 of row 0 and seats [0, 3] of row 1.
bms.scatter(5, 1); // return False
// There is only one seat left in the hall.
Constraints:
1 <= n <= 5 * 104
1 <= m, k <= 109
0 <= maxRow <= n - 1
At most 5 * 104 calls in total will be made to gather and scatter.
Solutions
Solution 1: Segment Tree
From the problem description, we can deduce the following:
For the gather(k, maxRow) operation, the goal is to seat $k$ people on the same row with consecutive seats. In other words, we need to find the smallest row where the remaining seats are greater than or equal to $k$.
For the scatter(k, maxRow) operation, we just need to find $k$ seats in total, but we want to minimize the row number. Therefore, we need to find the first row that has more than $0$ seats remaining, allocate seats there, and continue searching for the rest.
We can implement this using a segment tree. Each segment tree node contains the following information:
l: The left endpoint of the node's interval
r: The right endpoint of the node's interval
s: The total remaining seats in the interval corresponding to the node
mx: The maximum remaining seats in the interval corresponding to the node
Note that the index range for the segment tree starts from $1$.
The operations of the segment tree are as follows:
build(u, l, r): Builds node $u$, corresponding to the interval $[l, r]$, and recursively builds its left and right children.
modify(u, x, v): Starting from node $u$, finds the first node corresponding to the interval $[l, r]$ where $l = r = x$, and modifies the s and mx values of this node to $v$, then updates the tree upwards.
query_sum(u, l, r): Starting from node $u$, calculates the sum of s values in the interval $[l, r]$.
query_idx(u, l, r, k): Starting from node $u$, finds the first node in the interval $[l, r]$ where mx is greater than or equal to $k$, and returns the left endpoint l of this node. When searching, we start from the largest interval $[1, maxRow]$. Since we need to find the leftmost node with mx greater than or equal to $k$, we check whether the mx of the first half of the interval meets the condition. If so, the answer is in the first half, and we recursively search that half. Otherwise, the answer is in the second half, and we search that half recursively.
pushup(u): Updates the information of node $u$ using the information from its children.
For the gather(k, maxRow) operation, we first use query_idx(1, 1, n, k) to find the first row where the remaining seats are greater than or equal to $k$, denoted as $i$. Then, we use query_sum(1, i, i) to get the remaining seats in this row, denoted as $s$. Next, we use modify(1, i, s - k) to modify the remaining seats of this row to $s - k$, and update the tree upwards. Finally, we return the result $[i - 1, m - s]$.
For the scatter(k, maxRow) operation, we first use query_sum(1, 1, maxRow) to calculate the total remaining seats in the first $maxRow$ rows, denoted as $s$. If $s \lt k$, there are not enough seats, so we return false. Otherwise, we use query_idx(1, 1, maxRow, 1) to find the first row where the remaining seats are greater than or equal to $1$, denoted as $i$. Starting from this row, we use query_sum(1, i, i) to get the remaining seats in row $i$, denoted as $s_i$. If $s_i \geq k$, we directly use modify(1, i, s_i - k) to modify the remaining seats of this row to $s_i - k$, update the tree upwards, and return true. Otherwise, we update $k = k - s_i$, modify the remaining seats of this row to $0$, and update the tree upwards. Finally, we return true.
Time complexity:
The initialization time complexity is $O(n)$.
The time complexity of gather(k, maxRow) is $O(\log n)$.
The time complexity of scatter(k, maxRow) is $O((n + q) \times \log n)$.
The overall time complexity is $O(n + q \times \log n)$, and the space complexity is $O(n)$. Here, $n$ is the number of rows, and $q$ is the number of operations.
classNode:__slots__="l","r","s","mx"def__init__(self):self.l=self.r=0self.s=self.mx=0classSegmentTree:def__init__(self,n,m):self.m=mself.tr=[Node()for_inrange(n<<2)]self.build(1,1,n)defbuild(self,u,l,r):self.tr[u].l,self.tr[u].r=l,rifl==r:self.tr[u].s=self.tr[u].mx=self.mreturnmid=(l+r)>>1self.build(u<<1,l,mid)self.build(u<<1|1,mid+1,r)self.pushup(u)defmodify(self,u,x,v):ifself.tr[u].l==xandself.tr[u].r==x:self.tr[u].s=self.tr[u].mx=vreturnmid=(self.tr[u].l+self.tr[u].r)>>1ifx<=mid:self.modify(u<<1,x,v)else:self.modify(u<<1|1,x,v)self.pushup(u)defquery_sum(self,u,l,r):ifself.tr[u].l>=landself.tr[u].r<=r:returnself.tr[u].smid=(self.tr[u].l+self.tr[u].r)>>1v=0ifl<=mid:v+=self.query_sum(u<<1,l,r)ifr>mid:v+=self.query_sum(u<<1|1,l,r)returnvdefquery_idx(self,u,l,r,k):ifself.tr[u].mx<k:return0ifself.tr[u].l==self.tr[u].r:returnself.tr[u].lmid=(self.tr[u].l+self.tr[u].r)>>1ifself.tr[u<<1].mx>=k:returnself.query_idx(u<<1,l,r,k)ifr>mid:returnself.query_idx(u<<1|1,l,r,k)return0defpushup(self,u):self.tr[u].s=self.tr[u<<1].s+self.tr[u<<1|1].sself.tr[u].mx=max(self.tr[u<<1].mx,self.tr[u<<1|1].mx)classBookMyShow:def__init__(self,n:int,m:int):self.n=nself.tree=SegmentTree(n,m)defgather(self,k:int,maxRow:int)->List[int]:maxRow+=1i=self.tree.query_idx(1,1,maxRow,k)ifi==0:return[]s=self.tree.query_sum(1,i,i)self.tree.modify(1,i,s-k)return[i-1,self.tree.m-s]defscatter(self,k:int,maxRow:int)->bool:maxRow+=1ifself.tree.query_sum(1,1,maxRow)<k:returnFalsei=self.tree.query_idx(1,1,maxRow,1)forjinrange(i,self.n+1):s=self.tree.query_sum(1,j,j)ifs>=k:self.tree.modify(1,j,s-k)returnTruek-=sself.tree.modify(1,j,0)returnTrue# Your BookMyShow object will be instantiated and called as such:# obj = BookMyShow(n, m)# param_1 = obj.gather(k,maxRow)# param_2 = obj.scatter(k,maxRow)
classNode{intl,r;longmx,s;}classSegmentTree{privateNode[]tr;privateintm;publicSegmentTree(intn,intm){this.m=m;tr=newNode[n<<2];for(inti=0;i<tr.length;++i){tr[i]=newNode();}build(1,1,n);}privatevoidbuild(intu,intl,intr){tr[u].l=l;tr[u].r=r;if(l==r){tr[u].s=m;tr[u].mx=m;return;}intmid=(l+r)>>1;build(u<<1,l,mid);build(u<<1|1,mid+1,r);pushup(u);}publicvoidmodify(intu,intx,longv){if(tr[u].l==x&&tr[u].r==x){tr[u].s=v;tr[u].mx=v;return;}intmid=(tr[u].l+tr[u].r)>>1;if(x<=mid){modify(u<<1,x,v);}else{modify(u<<1|1,x,v);}pushup(u);}publiclongquerySum(intu,intl,intr){if(tr[u].l>=l&&tr[u].r<=r){returntr[u].s;}intmid=(tr[u].l+tr[u].r)>>1;longv=0;if(l<=mid){v+=querySum(u<<1,l,r);}if(r>mid){v+=querySum(u<<1|1,l,r);}returnv;}publicintqueryIdx(intu,intl,intr,intk){if(tr[u].mx<k){return0;}if(tr[u].l==tr[u].r){returntr[u].l;}intmid=(tr[u].l+tr[u].r)>>1;if(tr[u<<1].mx>=k){returnqueryIdx(u<<1,l,r,k);}if(r>mid){returnqueryIdx(u<<1|1,l,r,k);}return0;}privatevoidpushup(intu){tr[u].s=tr[u<<1].s+tr[u<<1|1].s;tr[u].mx=Math.max(tr[u<<1].mx,tr[u<<1|1].mx);}}classBookMyShow{privateintn;privateintm;privateSegmentTreetree;publicBookMyShow(intn,intm){this.n=n;this.m=m;tree=newSegmentTree(n,m);}publicint[]gather(intk,intmaxRow){++maxRow;inti=tree.queryIdx(1,1,maxRow,k);if(i==0){returnnewint[]{};}longs=tree.querySum(1,i,i);tree.modify(1,i,s-k);returnnewint[]{i-1,(int)(m-s)};}publicbooleanscatter(intk,intmaxRow){++maxRow;if(tree.querySum(1,1,maxRow)<k){returnfalse;}inti=tree.queryIdx(1,1,maxRow,1);for(intj=i;j<=n;++j){longs=tree.querySum(1,j,j);if(s>=k){tree.modify(1,j,s-k);returntrue;}k-=s;tree.modify(1,j,0);}returntrue;}}/** * Your BookMyShow object will be instantiated and called as such: * BookMyShow obj = new BookMyShow(n, m); * int[] param_1 = obj.gather(k,maxRow); * boolean param_2 = obj.scatter(k,maxRow); */
classNode{public:intl,r;longs,mx;};classSegmentTree{public:SegmentTree(intn,intm){this->m=m;tr.resize(n<<2);for(inti=0;i<n<<2;++i){tr[i]=newNode();}build(1,1,n);}voidmodify(intu,intx,intv){if(tr[u]->l==x&&tr[u]->r==x){tr[u]->s=tr[u]->mx=v;return;}intmid=(tr[u]->l+tr[u]->r)>>1;if(x<=mid){modify(u<<1,x,v);}else{modify(u<<1|1,x,v);}pushup(u);}longquerySum(intu,intl,intr){if(tr[u]->l>=l&&tr[u]->r<=r){returntr[u]->s;}intmid=(tr[u]->l+tr[u]->r)>>1;longv=0;if(l<=mid){v+=querySum(u<<1,l,r);}if(r>mid){v+=querySum(u<<1|1,l,r);}returnv;}intqueryIdx(intu,intl,intr,intk){if(tr[u]->mx<k){return0;}if(tr[u]->l==tr[u]->r){returntr[u]->l;}intmid=(tr[u]->l+tr[u]->r)>>1;if(tr[u<<1]->mx>=k){returnqueryIdx(u<<1,l,r,k);}if(r>mid){returnqueryIdx(u<<1|1,l,r,k);}return0;}private:vector<Node*>tr;intm;voidbuild(intu,intl,intr){tr[u]->l=l;tr[u]->r=r;if(l==r){tr[u]->s=m;tr[u]->mx=m;return;}intmid=(l+r)>>1;build(u<<1,l,mid);build(u<<1|1,mid+1,r);pushup(u);}voidpushup(intu){tr[u]->s=tr[u<<1]->s+tr[u<<1|1]->s;tr[u]->mx=max(tr[u<<1]->mx,tr[u<<1|1]->mx);}};classBookMyShow{public:BookMyShow(intn,intm){this->n=n;this->m=m;tree=newSegmentTree(n,m);}vector<int>gather(intk,intmaxRow){++maxRow;inti=tree->queryIdx(1,1,maxRow,k);if(i==0){return{};}longs=tree->querySum(1,i,i);tree->modify(1,i,s-k);return{i-1,(int)(m-s)};}boolscatter(intk,intmaxRow){++maxRow;if(tree->querySum(1,1,maxRow)<k){returnfalse;}inti=tree->queryIdx(1,1,maxRow,1);for(intj=i;j<=n;++j){longs=tree->querySum(1,j,j);if(s>=k){tree->modify(1,j,s-k);returntrue;}k-=s;tree->modify(1,j,0);}returntrue;}private:SegmentTree*tree;intm,n;};/** * Your BookMyShow object will be instantiated and called as such: * BookMyShow* obj = new BookMyShow(n, m); * vector<int> param_1 = obj->gather(k,maxRow); * bool param_2 = obj->scatter(k,maxRow); */
typeBookMyShowstruct{n,minttree*segmentTree}funcConstructor(nint,mint)BookMyShow{returnBookMyShow{n,m,newSegmentTree(n,m)}}func(this*BookMyShow)Gather(kint,maxRowint)[]int{maxRow++i:=this.tree.queryIdx(1,1,maxRow,k)ifi==0{return[]int{}}s:=this.tree.querySum(1,i,i)this.tree.modify(1,i,s-k)return[]int{i-1,this.m-s}}func(this*BookMyShow)Scatter(kint,maxRowint)bool{maxRow++ifthis.tree.querySum(1,1,maxRow)<k{returnfalse}i:=this.tree.queryIdx(1,1,maxRow,1)forj:=i;j<=this.n;j++{s:=this.tree.querySum(1,j,j)ifs>=k{this.tree.modify(1,j,s-k)returntrue}k-=sthis.tree.modify(1,j,0)}returntrue}typenodestruct{l,r,s,mxint}typesegmentTreestruct{tr[]*nodemint}funcnewSegmentTree(n,mint)*segmentTree{tr:=make([]*node,n<<2)fori:=rangetr{tr[i]=&node{}}t:=&segmentTree{tr,m}t.build(1,1,n)returnt}func(t*segmentTree)build(u,l,rint){t.tr[u].l,t.tr[u].r=l,rifl==r{t.tr[u].s,t.tr[u].mx=t.m,t.mreturn}mid:=(l+r)>>1t.build(u<<1,l,mid)t.build(u<<1|1,mid+1,r)t.pushup(u)}func(t*segmentTree)modify(u,x,vint){ift.tr[u].l==x&&t.tr[u].r==x{t.tr[u].s,t.tr[u].mx=v,vreturn}mid:=(t.tr[u].l+t.tr[u].r)>>1ifx<=mid{t.modify(u<<1,x,v)}else{t.modify(u<<1|1,x,v)}t.pushup(u)}func(t*segmentTree)querySum(u,l,rint)int{ift.tr[u].l>=l&&t.tr[u].r<=r{returnt.tr[u].s}mid:=(t.tr[u].l+t.tr[u].r)>>1v:=0ifl<=mid{v=t.querySum(u<<1,l,r)}ifr>mid{v+=t.querySum(u<<1|1,l,r)}returnv}func(t*segmentTree)queryIdx(u,l,r,kint)int{ift.tr[u].mx<k{return0}ift.tr[u].l==t.tr[u].r{returnt.tr[u].l}mid:=(t.tr[u].l+t.tr[u].r)>>1ift.tr[u<<1].mx>=k{returnt.queryIdx(u<<1,l,r,k)}ifr>mid{returnt.queryIdx(u<<1|1,l,r,k)}return0}func(t*segmentTree)pushup(uint){t.tr[u].s=t.tr[u<<1].s+t.tr[u<<1|1].st.tr[u].mx=max(t.tr[u<<1].mx,t.tr[u<<1|1].mx)}/** * Your BookMyShow object will be instantiated and called as such: * obj := Constructor(n, m); * param_1 := obj.Gather(k,maxRow); * param_2 := obj.Scatter(k,maxRow); */