Get this book > Problems on Array: For Interviews and Competitive Programming
In this article, we have solved the problem of Booking Concert Tickets in Groups. This involve the concept of Binary Indexed Tree and Segment Tree.
Prerequisites
Problem statement
People want to book tickets to a concert in groups of k
people.
The hall has n
rows and m
seats in each row. There are two types of groups : gather and scatter
They all prefer to be together while seating.
 Gather groups: They will only book if all the k members gets seats together ie, next to each other in the same row, and if one of them doesn't get it the whole group doesn't book the tickets. If they get allotted then return the coordinate of the starting seat for the group.
 Scatter groups: People in these groups have to be scattered in the hall, and they will only book if all of them receives a seat. So if all of them gets a seat then return true, else return false.
In both cases whole group will only book the tickets if all the members in the group can get a row number less than or equal to maxRow
value. The maxRow
value is different for each group. If there are multiple options available then the one with smallest row or column will be chosen.
Example
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.
Observation
 There are two group of people
 For each function call we have to allocate seats for
k
number of people and wont book the seats if any of their seat is in the row grater thanmaxRow
 We have to allocate seat with minimum row and column value in case multiple choices are there.
Approach 1
Here we will discuss how to solve this problem using binary indexed tree (BIT). BIT is popularly known as fenwick tree.
Intuitive steps
Scatter
 Calculate number of available seats till maxRow
.
 Return false
if allotted seats + k > total seats
 Else iterate through each row and allocate seats until k = 0
starting from start
.
 When k = 0
the function updates the start
and returns true
.
Gather
 Check if k seats are available till
maxRow
 start iteration from
i
tomaxRow
 In each iteration check if
k
seats are there or not  If yes, do necessary updates and return the
{i, g[i]  k}
 Else return
{}
outside the loop
Explained

First inside the class we will create an array
bt
which will represent the BST for our program, then we will initialize array g (which is responsible for storing the seats which is already allotted in each row), variables liken
(rows of seats present),m
(columns of seats present),start
(row number from which the next group will be allotted). Now we will have a constructor for the class which takes inn
,m
and initializes then
andm
member variables with their respective values, and does nothing else. 
Scatter
 When the scatter function is called the group size
k
and themaxRow
value is passed to it. So we will first use themaxRow
andprefix_sum()
function to get the total number of seats that got alloted.  Inside
prefix_sum
it initializessum = 0
and takes in a valuei
, then it enters a loop untili>0
. In each iterationi & (i)
computes the bitwise AND ofi
with its two's complement. This will isolate the least significant bit ofi
. Then the result will be subtracted fromi
. In each looping the value ofbt[i]
is added to thesum
variable. Thesum
is returned when the loop breaks.  The obtained value
sum
is stored inside the total variable, which is the total number of seats booked until themaxRow
. Once we get the total seats allotted we will check iftotal + k > ((long long)maxRow + 1) * m
, if its a yes then it means that there are no adequate number of seats available in the hall and this returns false. If its not then the execution continues.  Now we will start our iteration from the start (equals to 0 in the starting) variable and then books all
k
seats required. The loop continues till thei
value is less than or equal tomaxRow
.  In each iteration first we will check if any seats are empty in the current row or not.
mg[i]
will give the number of seats available in that particular row, if no seats are available we will update our start toi+1
and continue our loop.  If seats are available then we initializes the number of seats that can be allotted to
min(mg[i], k)
and then we will reducek
by take and take number of people got allotted. Now we will call theadd()
and pass in the i and k.  In the add function we will take the
i
(represents the index), andval
(the value that needed to be added). To update the BIT array, we start from the given indexi
and add val to the element at that index. The iteration will be in such a way that we will update the elements in the BIT array that represent the parent nodes of the given index. We do this by adding the same valueval
to the elements at the index which are obtained by flipping the rightmost set bit ofi
(obtained by performingi & (i))
and adding it toi
. This operation is repeated until we reach the end of the BIT array.  In the end after the loop we return
true
.
 When the scatter function is called the group size

Gather
 Like in scatter function here also we will first calculate the total seats allotted and check if
k
amount of seats is available in the hall untilmaxRow
or not. If its not available we will return and empty list{}
. If seats are available then the program continues.  We will start our iteration from
i
tillmaxRow
to find the row withk
seats to accommodate the group. In each iteration we will check ifk
seats are available or not, if its not thecontinue
statement is executed. Else we will addk
tog[i]
and then update thebt
array usingadd()
. Then we will return the indexes of the first seat for the group which would be{i, g[i]  k}
. If we don't find such a case then an empty array is returned outside the loop.
 Like in scatter function here also we will first calculate the total seats allotted and check if
Code:
#include <iostream>
#include <vector>
using namespace std;
class BookMyShow {
public:
constexpr int static max_n = 50001;
long long bt[max_n + 1] = {};
long long prefix_sum(int i)
{
long long sum = 0;
for (i = i + 1; i > 0; i = i & (i))
sum += bt[i];
return sum;
}
void add(int i, int val)
{
for (i = i + 1; i <= max_n; i += i & (i))
bt[i] += val;
}
int g[50001] = {}, n = 0, m = 0, start = 0;
BookMyShow(int n, int m) : n(n), m(m) { }
vector<int> gather(int k, int maxRow) {
long long total = prefix_sum(maxRow);
if (total + k > ((long long)maxRow + 1) * m)
return {};
for (int i = start; i <= maxRow; ++i) {
if (g[i] + k > m)
continue;
g[i] += k;
add(i, k);
return {i, g[i]  k};
}
return {};
}
bool scatter(int k, int maxRow) {
long long total = prefix_sum(maxRow);
if (total + k > ((long long)maxRow + 1) * m)
return false;
for (int i = start; k && i <= maxRow; ++i) {
if (m  g[i]) {
int take = min(m  g[i], k);
k = take;
add(i, take);
g[i] += take;
}
else
start = i + 1;
}
return true;
}
};
/**
* 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);
*/
int main() {
int n, m, choice, k, rowMax;
cout << "Enter number of rows: ";
cin >> n;
cout << "Enter number of seats per row: ";
cin >> m;
BookMyShow bms(n, m);
bool success = false;
vector<int> seat;
do {
cout << "\n\n1. Scatter" << endl;
cout << "2. Gather" << endl;
cout << "3. Quit" << endl;
cout << "Enter choice: ";
cin >> choice;
switch (choice) {
case 1:
cout << "Enter k: ";
cin >> k;
cout << "Enter rowMax: ";
cin >> rowMax;
success = bms.scatter(k, rowMax);
if (success) {
cout << "Scatter successful!" << endl;
} else {
cout << "Scatter failed: not enough seats available!" << endl;
}
break;
case 2:
cout << "Enter k: ";
cin >> k;
cout << "Enter rowMax: ";
cin >> rowMax;
seat = bms.gather(k, rowMax);
if (seat.empty()) {
cout << "Gather failed: not enough seats available!" << endl;
} else {
cout << "Gather successful! Seat " << seat[0] << "" << seat[1] << " reserved." << endl;
}
break;
case 3:
cout << "Exiting program..." << endl;
break;
default:
cout << "Invalid choice! Please try again." << endl;
break;
}
} while (choice != 3);
return 0;
}
Output:
Enter number of rows: 2
Enter number of seats per row: 5
1. Scatter
2. Gather
3. Quit
Enter choice: 2
Enter k: 4
Enter rowMax: 0
Gather successful! Seat 00 reserved.
1. Scatter
2. Gather
3. Quit
Enter choice: 2
Enter k: 2
Enter rowMax: 0
Gather failed: not enough seats available!
1. Scatter
2. Gather
3. Quit
Enter choice: 1
Enter k: 5
Enter rowMax: 1
Scatter successful!
1. Scatter
2. Gather
3. Quit
Enter choice: 1
Enter k: 5
Enter rowMax: 1
Scatter failed: not enough seats available!
1. Scatter
2. Gather
3. Quit
Enter choice: 3
Exiting program...
Complexities
In BIT while performing prefix sum and update operation we start from the index i and move towards the root of the tree by using the property of binary representation. At each step we add the value stored at the current node to the sum and move to the parent node. This process is continued till we reach the root of the tree. Since the height of the tree will be log n
the time complexity will also be log n
. To make this operation to be feasible the space complexity will be O(n+1)
, as the size of the array is n+1
.
Both gather()
and scatter()
function uses fenwick tree to calculate the prefix sum and for updating. Hence the time complexity of both these functions will be O(n log m)
. So the time complexity of the whole program will be O(n log m)
.
Both these functions use BIT for calculation hence the space complexity of the program will be O(n+1)
.
Approach 2
Here we will be using segment tree to solve this question
Intuitive steps
 Initialize a segment tree
 Add a function to perform range sum query
 Gather function
 Obtain index of first row which at least have
k
available seats  If its not there return
{}
 If its there
g[i]
is updated tog[i]+k
 Then update the segment tree
 Return
{i
,g[i]  k}
the index of the start seat
 Obtain index of first row which at least have
 Scatter function
 Check if k number of seats are available until
maxRow
 If it is return
false
 Iterate from start till
maxRow
 Check if seats are available for each row
 If its there, update
g[i]
and the segment tree  else update the start with
i+1
 When the loop breaks return
true
 Check if k number of seats are available until
Explained

First we will initialize a segment tree
st
, then an arrayg
(which represents the number of booked seats in each row),n
(rows in the hall),m
(columns in the hall),start
(represents the row number from which the assignment of the seats should start) and a constructor which assignn
,m
and additionally the segment treest
is initialized as a vector of pairs with size n*4, and each pair is initialized with the values{0, m}
. This sets the initial sum of each range in the tree to 0 and maximum value in each range tom
, as all rows are initially empty som
seats are available. 
We need a function which calculates the sum of values in the given range of indexes of the tree. For this we will create a query function. The function takes five arguments:
tl
,tr
,l
,r
, andp
(defaulted to 1). These arguments represent the current node's left and right index, the query's left and right indexes, and the current node's index in the segment tree, respectively. 
Now inside the query function we will check if
l>r
if it is the range query is invalid and we will return0
. Now we will check ifl
andr
are equal totl
andtr
respectively. If yes it means that the current node is representing the leaf node in the segment tree and the value can be returned directly. These were the base cases, if none are triggered we continue in our execution. 
Since the base cases were not triggered the function calculates the mid point
tm
of the current nodes range using(tl+tr)/2
. Now we will call the function recursively twice with updated arguments. The first call (tl
,tm
,l
,min(r, tm), p _ 2)
handles the left of the current nodes range and second call(tm + 1, tr, max(l, tm + 1), r, p _ 2 + 1)
handles the right of the current nodes range. Then it returns the sum of the two recursive calls, which represents the sum of the query range within the current node's range. 
Now, we need a function which could give us the index of the first element in the segment tree whose value is greater than or equal to the given value x. So we will create the function
get_first_idx
. The function takes four arguments:lv
,rv
,x
, andp
.lv
andrv
specify the range of indexes in the segment tree thatp
represents.x
is the value we want to find the first index greater than or equal to.p
is the index of the current node in the segment tree. The default value of p is 1, which represents the root node of the segment tree. 
Inside the function we will check if the current node value is less than x, if it is that means that the subtree wont have an element greater than that, hence return
1
to indicate that. If its not then we will check if it is the leaf node or not(lv == rv)
, if it is then that is the first element greater than or equal to x, so we will returnlv
. If its not the leaf node then we calculate the the midpoint of the rangelv
,lr
then recursively search either the leftot
the right subtree depending on the value of the left child node. If its greater then search left else the right. The mid value will be updated for each recursive call. The moment we find an element greater than or equal tox
we will return its index, else we will continue our search in right sub tree. If we reach the leaf node in right sub tree then we will return1
, as there will be no element greater thanx
. 
After each change we need to update the change, so for that we will create another function called
update()
. The update function is called withtl
andtr
representing the left and right bounds of the current segment of the segment tree,pos
representing the position of the element being updated, new_val representing the new value of the element being updated, andp
representing the current node of the segment tree. Now we will check if the left and right bounds of the current segment are equal. If yes, the current node is a leaf node and we have to update it with new value and the difference betweenm
and the new value, asm
is the total available seats and we do this step to keep a track of it. 
If the left and right bounds of the current segment are not equal then we need to update the child nodes of that node, and for that we will calculate the mid
tm
. If thepos
value is less than or equal to the middle point, then we will update the left child of the current node by recursively calling the update function with left segment boundstl
andtm
. If its greater then we will do the same for the right sub tree. 
After updating the child nodes, we will update the current node by setting its value to the sum of the values of its child nodes and maximum of the differences between
m
and its child nodes. Its done to keep a track on the available tickets in any row. 
Gather function
 Here we will first call the
get_first_idx()
to find the index of the first row in the hall layout whose number of available seats is greater than or equal tok
. If it returns a negative index or if it returns an index greater thanmaxRow
then the function returns an empty vector.  If a row is present then we will update the
g[i]
. Then we will update the segment tree using the update function.  In the end it returns the first index of the seat which got reserved
{i, g[i]k}
.
 Here we will first call the

Scatter function
 First we will check if the k is exceeding the capacity of the hall or not. We do it by comparing
total tickets sold + k with the capacity of the hall
. If it exceeds we will returnfalse
.  Now we will start our loop from
start
tomaxRow
. For each row we will check if there are any seats available.  If its there the function calculates the number of tickets that can be sold in that row by taking the minimum value between
k
andmg[i]
. After this we will update the number of tickets sold in the arrayg
, by adding the previously calculated value. Then we will update the segment tree by calling the update function.  In the end after ending the loop, it returns
true
.
 First we will check if the k is exceeding the capacity of the hall or not. We do it by comparing
Code
#include <iostream>
#include <vector>
using namespace std;
class BookMyShow {
public:
vector<pair<long long, int>> st;
int g[50001] = {}, n = 0, m = 0, start = 0;
long long query(int tl, int tr, int l, int r, int p = 1) {
if (l > r)
return 0;
if (l == tl && r == tr)
return st[p].first;
int tm = (tl + tr) / 2;
return query(tl, tm, l, min(r, tm), p * 2) + query(tm + 1, tr, max(l, tm + 1), r, p * 2 + 1);
}
int get_first_idx(int lv, int rv, int x, int p = 1) {
if (st[p].second < x)
return 1;
while (lv != rv) {
int mid = lv + (rv  lv) / 2;
if (st[2 * p].second >= x) {
p *= 2;
rv = mid;
} else {
p = 2 * p + 1;
lv = mid + 1;
}
}
return lv;
}
void update(int tl, int tr, int pos, int new_val, int p = 1) {
if (tl == tr)
st[p] = {new_val, m  new_val};
else {
int tm = (tl + tr) / 2;
if (pos <= tm)
update(tl, tm, pos, new_val, p * 2);
else
update(tm + 1, tr, pos, new_val, p * 2 + 1);
st[p] = {st[p * 2].first + st[p * 2 + 1].first, max(st[p * 2].second, st[p * 2 + 1].second)};
}
}
BookMyShow(int n, int m) : n(n), m(m) {
st = vector<pair<long long, int>>(n * 4, {0, m});
}
vector<int> gather(int k, int maxRow) {
int i = get_first_idx(0, n  1, k);
if (i < 0  i > maxRow)
return {};
g[i] += k;
update(0, n  1, i, g[i]);
return {i, g[i]  k};
}
bool scatter(int k, int maxRow) {
if (query(0, n  1, 0, maxRow) + k > ((long long)maxRow + 1) * m)
return false;
for (int i = start; k && i <= maxRow; ++i) {
if (m  g[i]) {
int take = min(m  g[i], k);
k = take;
g[i] += take;
update(0, n  1, i, g[i]);
}
else
start = i + 1;
}
return true;
}
};
int main() {
int n, m, choice, k, rowMax;
cout << "Enter number of rows: ";
cin >> n;
cout << "Enter number of seats per row: ";
cin >> m;
BookMyShow bms(n, m);
bool success = false;
vector<int> seat;
do {
cout << "\n\n1. Scatter" << endl;
cout << "2. Gather" << endl;
cout << "3. Quit" << endl;
cout << "Enter choice: ";
cin >> choice;
switch (choice) {
case 1:
cout << "Enter k: ";
cin >> k;
cout << "Enter rowMax: ";
cin >> rowMax;
success = bms.scatter(k, rowMax);
if (success) {
cout << "Scatter successful!" << endl;
} else {
cout << "Scatter failed: not enough seats available!" << endl;
}
break;
case 2:
cout << "Enter k: ";
cin >> k;
cout << "Enter rowMax: ";
cin >> rowMax;
seat = bms.gather(k, rowMax);
if (seat.empty()) {
cout << "Gather failed: not enough seats available!" << endl;
} else {
cout << "Gather successful! Seat " << seat[0] << "" << seat[1] << " reserved." << endl;
}
break;
case 3:
cout << "Exiting program..." << endl;
break;
default:
cout << "Invalid choice! Please try again." << endl;
break;
}
} while (choice != 3);
return 0;
}
Complexity Analysis
Complexity mainly depends on the query()
, update()
and get_first_idx()
.
get_first_idx()
function: The time complexity of theget_first_idx()
function isO(log n)
wheren
is the number of elements in the segment tree. This is because the function performs a binary search on the segment tree to find the first index whose value is greater than or equal to the given valuex
.update()
function: The time complexity of theupdate()
function is alsoO(log n)
wheren
is the number of elements in the segment tree. This is because the function updates the value of a node in the segment tree by traversing down from the root to the leaf node.query()
function: The time complexity of thequery()
function isO(log n)
wheren
is the number of elements in the segment tree. This is because the function performs a binary search on the segment tree to find the sum of values within a range.
Inside the scatter()
, we do use a loop which runs for maxRow
number of times. Hence we can say that the total time complexity of the program would be O(log n + maxRow)
.
The space complexity of this solution is O(N log N)
, where N
is the total number of seats in the theater. This is because we are creating a segment tree with 4*N
nodes, where N
is the number of seats in the theater, and the height of the tree is log N
. Each node in the segment tree requires a pair of values, so the total space required is O(N log N)
.
Output
Enter number of rows: 2
Enter number of seats per row: 5
1. Scatter
2. Gather
3. Quit
Enter choice: 2
Enter k: 4
Enter rowMax: 0
Gather successful! Seat 00 reserved.
1. Scatter
2. Gather
3. Quit
Enter choice: 2
Enter k: 2
Enter rowMax: 0
Gather failed: not enough seats available!
1. Scatter
2. Gather
3. Quit
Enter choice: 1
Enter k: 5
Enter rowMax: 1
Scatter successful!
1. Scatter
2. Gather
3. Quit
Enter choice: 1
Enter k: 5
Enter rowMax: 1
Scatter failed: not enough seats available!
1. Scatter
2. Gather
3. Quit
Enter choice: 3
Exiting program...
With this article at OpenGenus, you must have the complete idea of solving this problem of booking concert tickets.