Booking Concert Tickets in Groups [using BIT and Segment Tree]

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.

Pre-requisites

• Binary Indexed Tree (BIT)
• Segmented tree

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 co-ordinate 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 than maxRow
• 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 to maxRow
• 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 like n (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 in n, m and initializes the n and m member variables with their respective values, and does nothing else.

• Scatter

  • When the scatter function is called the group size k and the maxRow value is passed to it. So we will first use the maxRow and prefix_sum() function to get the total number of seats that got alloted.
  • Inside prefix_sum it initializes sum = 0 and takes in a value i, then it enters a loop until i>0. In each iteration i & (-i) computes the bitwise AND of i with its two's complement. This will isolate the least significant bit of i. Then the result will be subtracted from i. In each looping the value of bt[i] is added to the sum variable. The sum 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 the maxRow. Once we get the total seats allotted we will check if total + 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 the i value is less than or equal to maxRow.
  • In each iteration first we will check if any seats are empty in the current row or not. m-g[i] will give the number of seats available in that particular row, if no seats are available we will update our start to i+1 and continue our loop.
  • If seats are available then we initializes the number of seats that can be allotted to min(m-g[i], k) and then we will reduce k by take and take number of people got allotted. Now we will call the add() and pass in the i and k.
  • In the add function we will take the i (represents the index), and val (the value that needed to be added). To update the BIT array, we start from the given index i 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 value val to the elements at the index which are obtained by flipping the rightmost set bit of i (obtained by performing i & (-i)) and adding it to i. This operation is repeated until we reach the end of the BIT array.
  • In the end after the loop we return true.

• 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 until maxRow 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 till maxRow to find the row with k seats to accommodate the group. In each iteration we will check if kseats are available or not, if its not the continue statement is executed. Else we will add k to g[i] and then update the bt array using add(). 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.

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 0-0 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 to g[i]+k
  • Then update the segment tree
  • Return {i, g[i] - k} the index of the start seat
• 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

Explained

• First we will initialize a segment tree st, then an array g (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 assign n, m and additionally the segment tree st 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 to m, as all rows are initially empty so m 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, and p (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 return 0. Now we will check if l and r are equal to tl and tr 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, and p. lv and rv specify the range of indexes in the segment tree that p 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 return lv. If its not the leaf node then we calculate the the midpoint of the range lv, lr then recursively search either the left ot 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 to x 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 return -1, as there will be no element greater than x.

• After each change we need to update the change, so for that we will create another function called update(). The update function is called with tl and tr 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, and p 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 between m and the new value, as m 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 the pos 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 bounds tl and tm. 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 to k. If it returns a negative index or if it returns an index greater than maxRow 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}.

• 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 return false.
  • Now we will start our loop from start to maxRow. 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 and m-g[i]. After this we will update the number of tickets sold in the array g, 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.

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 the get_first_idx() function is O(log n) where n 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 value x.
• update() function: The time complexity of the update() function is also O(log n) where n 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 the query() function is O(log n) where n 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 0-0 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.