2286. Booking Concert Tickets in Groups

HardDesignBinary Indexed TreeSegment TreeBinary Search
Leetcode Link

Problem Description

The given LeetCode problem describes a situation in which we need to develop a ticketing system for a concert hall with a certain number of rows and seats. Specifically, the tasks are as follows:

  • The concert hall has 'n' rows with a number of 'm' seats in each row.

  • When a group of 'k' spectators come to watch a concert, they either want to sit together in one row or agree to sit separately.

  • The ticketing system should allocate seats with row numbers less than or equal to 'maxRow', which is different for each group.

  • Spectators will only be satisfied with the smallest available row and the smallest available seat in that row.

  • There is a need to implement three methods:

    1. BookMyShow(int n, int m): This is a constructor that initializes the object with the number of rows and the number of seats per row.
    2. int[] gather(int k, int maxRow): This method should return an array with 2 elements indicating the row and seat number where the group of 'k' spectators can sit together in a consecutive block. If it's not possible to find such a block, an empty array should be returned.
    3. boolean scatter(int k, int maxRow): This method should return true if we can allocate seats for all 'k' spectators in any rows from 0 to 'maxRow'. If the allocation is possible, then seats should be given out starting with the smallest row number and the smallest seat number in each row.

The algorithm aims to efficiently manage the seating arrangement with the capability of instantaneously checking available seats, booking seats for a group either together or scattered across different rows, and making smart choices to satisfy spectators by meeting their preference for sitting in lower-numbered rows and seats to the best possible extent.

Intuition

The solution makes use of a Segment Tree, which is a powerful data structure that allows for efficient range queries and updates. The segment tree is initialized to store the number of available seats in each row, as well as the maximum number of consecutive available seats in any segment of rows.

  • To implement the gather operation, the segment tree is queried to find the row where there is a block of 'k' consecutive seats available using the query_idx function. If such a row is found, the starting seat number is computed, the seats are marked as occupied, and the row and starting seat number are returned.
  • To implement the scatter operation, the segment tree is queried for the total number of seats available from row 0 to maxRow to check if there are enough seats to accommodate the group. If there are enough seats, the seats are allocated starting with the row with the smallest number, updating the available seats in the segment tree along the way until all 'k' group members have seats.

The key part of the solution lies in how the segment tree is structured and operated. Each node in the tree represents a range of rows and contains information about the total and maximum number of available seats in those rows. This allows the system to quickly ascertain whether there is a row with enough seats to accommodate a group and to locate and book these seats effectively.

Both operations rely on the segment tree's ability to combine information from child nodes when performing updates (pushup) or providing a sum of seats for a given range or querying for the first index where 'k' seats are available (query_idx, query_sum). This enables the system to make optimal seat allocation decisions quickly to satisfy the requirements of the gathered groups of spectators.

Learn more about Segment Tree and Binary Search patterns.

Solution Approach

The solution approach utilizes a segment tree, which is a data structure that efficiently supports range queries and updates, which are essential for implementing the ticketing system. The core logic involves two main parts: the construction of the segment tree and the methods to perform the gather and scatter operations.

Segment Tree Construction:

  • A custom Node class is created to represent each node of the segment tree, containing properties for managing the range (l, r), the sum of available seats (s), and the maximum consecutive available seats (mx) in that range.
  • The SegmentTree class is a specialized structure designed to perform the operations required by the ticketing system. It initializes the tree with 2n nodes to cover all individual rows and ranges of rows in the concert hall when built.
  • The build function recursively constructs the tree: if a node represents a single row, it sets s and mx to m, the total number of seats in a row. Otherwise, it assigns values based on the combination of its child nodes' values, with s being the sum of available seats (s from both children) and mx being the maximum consecutive available seats (max of mx from both children).

Implementing the gather and scatter methods:

  • Both gather and scatter methods operate on the segment tree utilizing different query and update strategies:
  • gather: Utilizes the query_idx function to find the first row that can accommodate k consecutive seats. This query checks the mx property in the nodes, returning the index of the row (if any) where the group can sit together. After finding such a row, it calls modify to update the tree, subtracting k from the sum of available seats and updating the mx value.
  • scatter: Invokes the query_sum function to compute the total number of available seats from row 0 to maxRow. Checks if the total is greater than or equal to k; if yes, proceeds to allocate seats. Through an iterative process, it updates rows one by one using the modify function until all group members have a seat. In each step, either the entire k is allocated to a row or just the remaining number of available seats, decrementing k accordingly until k reaches zero.

Segment Tree Queries and Updates:

  • The query_sum method calculates the sum of available seats in a specified range, efficiently adding the values from relevant nodes.
  • The query_idx function searches for the row index where k consecutive seats can be found, zeroing in on the segment of the tree that meets this condition.
  • The modify function updates a particular row (identified by index x) with the new value 'v', which represents the updated number of seats after an allocation. The updates are propagated up the tree using the pushup method to ensure that the parent nodes correctly reflect the changes below.

The combination of segment tree properties and the specific implementation of these methods ensure that the solution can allocate seats both individually and as a contiguous block, meeting the constraints of the spectators while ensuring the performance is suitable for a real-time ticketing system.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a small example to illustrate the solution approach using the segment tree data structure for managing a concert hall ticket system.

Initial Setup: Suppose we have a concert hall with n = 3 rows and m = 5 seats per row. The SegmentTree is constructed this way: each leaf node corresponds to a row, initially having s = m (sum of available seats) and mx = m (maximum consecutive available seats).

Now, the tree would initially look something like this:

      Node1 (s=15, mx=5)
      /        \
Node2 (s=10, mx=5) Node3 (s=5, mx=5)
  /      \
Node4 (s=5, mx=5) Node5 (s=5, mx=5)

Gather Example: A group of k = 4 spectators wants to sit together and their maxRow is 2 (they are considering rows 0 to 2). They invoke int[] gather(k, maxRow).

  • We use query_idx to find the first row within maxRow where there are k consecutive seats available.
  • Starting from the root, we find that Node1, covering all rows, has mx = 5, which is enough. We dive into its left child, Node2 (mx = 5), and find it suitable.
  • We dive further and examine its children, Node4 and Node5. We go to the leftmost child that can accommodate the group, which is Node4 (mx = 5).
  • Node4 corresponds to row 0, which has enough space. We allocate seats 0 to 3 to the group and update the segment tree.

The segment tree will be updated to:

      Node1 (s=11, mx=5)
      /        \
Node2 (s=6, mx=1) Node3 (s=5, mx=5)
  /      \
Node4 (s=1, mx=1) Node5 (s=5, mx=5)

The gather method returns [0, 0], indicating the row and the seat number where the group can sit together.

Scatter Example: Another group of k = 6 spectators is fine with sitting separately, and their maxRow is 2. They call boolean scatter(k, maxRow).

  • We use query_sum to find out if there are at least k seats available in total from rows 0 to maxRow.
  • query_sum(0, 2) returns 11 (6 from Node2 + 5 from Node3), which is more than k.
  • We allocate seats to the group one row at a time until we place all k members.

Allocation process:

  • Allocate 1 seat in row 0 (Node4 has 1 seat available).
  • Allocate all 5 seats in row 1 (Node5 has 5 seats available).
  • The remaining group (k is now 0) can be allocated in row 2 (Node3 covers this).

The update process from modify function is applied after allocating each part of the group and the final segment tree looks like:

      Node1 (s=5, mx=5)
      /        \
Node2 (s=0, mx=0) Node3 (s=5, mx=5)
  /      \
Node4 (s=0, mx=0) Node5 (s=0, mx=0)

The scatter method returns true, indicating that all k spectators have been seated across the rows up to maxRow.

This example demonstrates how the segment tree manages seat allocations for both gather and scatter scenarios efficiently, taking advantage of the structure's ability to perform range queries and updates.

Solution Implementation

1from typing import List
2
3class Node:
4    def __init__(self):
5        # Initialize left and right pointers, sum, and max values
6        self.left = self.right = 0
7        self.sum_val = self.max_val = 0
8
9
10class SegmentTree:
11    def __init__(self, n, m):
12        # Initialize Segment Tree with size, default value m, and build the tree
13        self.size = m
14        self.tree_nodes = [Node() for _ in range(n << 2)]
15        self._build(1, 1, n)
16
17    def _build(self, idx, left, right):
18        # Build function to initialize the segment tree
19        self.tree_nodes[idx].left, self.tree_nodes[idx].right = left, right
20        if left == right:
21            # If it is a leaf node, assign sum and max with the size value
22            self.tree_nodes[idx].sum_val = self.tree_nodes[idx].max_val = self.size
23            return
24        mid = (left + right) >> 1
25        # Recursively build the left and right subtrees
26        self._build(idx << 1, left, mid)
27        self._build(idx << 1 | 1, mid + 1, right)
28        # Update current node's values based on the children nodes
29        self._pushup(idx)
30
31    def modify(self, idx, x, val):
32        # Modify the value at a position x with the value val
33        if self.tree_nodes[idx].left == x and self.tree_nodes[idx].right == x:
34            # If it is the exact position, update sum and max
35            self.tree_nodes[idx].sum_val = self.tree_nodes[idx].max_val = val
36            return
37        mid = (self.tree_nodes[idx].left + self.tree_nodes[idx].right) >> 1
38        if x <= mid:
39            # Modify the left subtree if x is in the left half
40            self.modify(idx << 1, x, val)
41        else:
42            # Otherwise, modify the right subtree
43            self.modify(idx << 1 | 1, x, val)
44        # Update the current node after modification
45        self._pushup(idx)
46
47    def query_sum(self, idx, left, right):
48        # Query the sum of values in the range [left, right]
49        if self.tree_nodes[idx].left >= left and self.tree_nodes[idx].right <= right:
50            # If the current segment is completely within range, return its sum
51            return self.tree_nodes[idx].sum_val
52        mid = (self.tree_nodes[idx].left + self.tree_nodes[idx].right) >> 1
53        val = 0
54        # Accumulate sum from left subtree if it intersects the range
55        if left <= mid:
56            val += self.query_sum(idx << 1, left, right)
57        # Accumulate sum from right subtree if it intersects the range
58        if right > mid:
59            val += self.query_sum(idx << 1 | 1, left, right)
60        return val
61
62    def query_idx(self, idx, left, right, k):
63        # Query position where value is at least k
64        if self.tree_nodes[idx].max_val < k:
65            # Return 0 if max value in this segment is less than k
66            return 0
67        if self.tree_nodes[idx].left == self.tree_nodes[idx].right:
68            # If it's a leaf node, return its position
69            return self.tree_nodes[idx].left
70        mid = (self.tree_nodes[idx].left + self.tree_nodes[idx].right) >> 1
71        if self.tree_nodes[idx << 1].max_val >= k:
72            # If left child has a max value greater or equal to k, search there
73            return self.query_idx(idx << 1, left, right, k)
74        if right > mid:
75            # Otherwise, search in the right subtree
76            return self.query_idx(idx << 1 | 1, left, right, k)
77        return 0
78
79    def _pushup(self, idx):
80        # Update the sum and max value for the idx node based on its children
81        self.tree_nodes[idx].sum_val = self.tree_nodes[idx << 1].sum_val + self.tree_nodes[idx << 1 | 1].sum_val
82        self.tree_nodes[idx].max_val = max(self.tree_nodes[idx << 1].max_val, self.tree_nodes[idx << 1 | 1].max_val)
83
84
85class BookMyShow:
86    def __init__(self, n: int, m: int):
87        # Initialize the BookMyShow with nrows, and a SegmentTree for seat handling
88        self.n_rows = n
89        self.segment_tree = SegmentTree(n, m)
90
91    def gather(self, k: int, max_row: int) -> List[int]:
92        # Attempt to book k contiguous seats up to and including max_row
93        max_row += 1
94        idx = self.segment_tree.query_idx(1, 1, max_row, k)
95        if idx == 0:
96            # If not successful, return an empty list
97            return []
98        sum_seats = self.segment_tree.query_sum(1, idx, idx)
99        self.segment_tree.modify(1, idx, sum_seats - k)
100        return [idx - 1, self.segment_tree.size - sum_seats]
101
102    def scatter(self, k: int, max_row: int) -> bool:
103        # Attempt to book k seats in total up to and including max_row (not necessarily contiguous)
104        max_row += 1
105        if self.segment_tree.query_sum(1, 1, max_row) < k:
106            # If insufficient seats are available, return False
107            return False
108        idx = self.segment_tree.query_idx(1, 1, max_row, 1)
109        for j in range(idx, self.n_rows + 1):
110            sum_seats = self.segment_tree.query_sum(1, j, j)
111            if sum_seats >= k:
112                # Book seats in the current row if possible and return True
113                self.segment_tree.modify(1, j, sum_seats - k)
114                return True
115            k -= sum_seats
116            # If insufficient seats in the row, set the seats to 0 and continue
117            self.segment_tree.modify(1, j, 0)
118        return True
119
120
121# You can instantiate the BookMyShow as follows:
122# obj = BookMyShow(n, m)
123# result_gather = obj.gather(k, maxRow)
124# result_scatter = obj.scatter(k, maxRow)
125
1class Node {
2    int left, right;
3    long max, sum;
4}
5
6class SegmentTree {
7    private Node[] tree;
8    private int seatsPerRow;
9
10    public SegmentTree(int rows, int seatsPerRow) {
11        this.seatsPerRow = seatsPerRow;
12        tree = new Node[rows << 2]; // 4 times the number of rows for segment tree nodes
13        for (int i = 0; i < tree.length; ++i) {
14            tree[i] = new Node();
15        }
16        build(1, 1, rows);
17    }
18
19    // Builds the segment tree
20    private void build(int index, int left, int right) {
21        tree[index].left = left;
22        tree[index].right = right;
23        if (left == right) {
24            // Leaf nodes represent individual rows
25            tree[index].sum = seatsPerRow;
26            tree[index].max = seatsPerRow;
27            return;
28        }
29        int mid = (left + right) >> 1;
30        build(index << 1, left, mid);
31        build(index << 1 | 1, mid + 1, right);
32        pushUp(index);
33    }
34
35    // Updates the value at a specific position
36    public void modify(int index, int position, long value) {
37        if (tree[index].left == position && tree[index].right == position) {
38            tree[index].sum = value;
39            tree[index].max = value;
40            return;
41        }
42        int mid = (tree[index].left + tree[index].right) >> 1;
43        if (position <= mid) {
44            modify(index << 1, position, value);
45        } else {
46            modify(index << 1 | 1, position, value);
47        }
48        pushUp(index);
49    }
50
51    // Calculate the sum of a range [l, r]
52    public long querySum(int index, int left, int right) {
53        if (tree[index].left >= left && tree[index].right <= right) {
54            return tree[index].sum;
55        }
56        int mid = (tree[index].left + tree[index].right) >> 1;
57        long total = 0;
58        if (left <= mid) {
59            total += querySum(index << 1, left, right);
60        }
61        if (right > mid) {
62            total += querySum(index << 1 | 1, left, right);
63        }
64        return total;
65    }
66
67    // Find the index where a consecutive block of seats starts that can fit 'k' people
68    public int queryIndex(int index, int left, int right, int k) {
69        if (tree[index].max < k) {
70            return 0;
71        }
72        if (tree[index].left == tree[index].right) {
73            return tree[index].left;
74        }
75        int mid = (tree[index].left + tree[index].right) >> 1;
76        if (tree[index << 1].max >= k) {
77            return queryIndex(index << 1, left, right, k);
78        }
79        if (right > mid) {
80            return queryIndex(index << 1 | 1, left, right, k);
81        }
82        return 0;
83    }
84
85    // Updates the parent node based on changes in its children
86    private void pushUp(int index) {
87        tree[index].sum = tree[index << 1].sum + tree[index << 1 | 1].sum;
88        tree[index].max = Math.max(tree[index << 1].max, tree[index << 1 | 1].max);
89    }
90}
91
92class BookMyShow {
93    private int rowCount;
94    private int seatsPerRow;
95    private SegmentTree segmentTree;
96
97    public BookMyShow(int rowCount, int seatsPerRow) {
98        this.rowCount = rowCount;
99        this.seatsPerRow = seatsPerRow;
100        segmentTree = new SegmentTree(rowCount, seatsPerRow);
101    }
102
103    // Tries to find a block of k consecutive seats in any row up to maxRow
104    public int[] gather(int k, int maxRow) {
105        ++maxRow; // To make it inclusive end index
106        int rowIndex = segmentTree.queryIndex(1, 1, maxRow, k);
107        if (rowIndex == 0) {
108            return new int[] {}; // No block found
109        }
110        long seatsAvailable = segmentTree.querySum(1, rowIndex, rowIndex);
111        segmentTree.modify(1, rowIndex, seatsAvailable - k);
112        return new int[] {rowIndex - 1, (int) (seatsPerRow - seatsAvailable)};
113    }
114
115    // Allocates seats one by one until it satisfies the request k
116    public boolean scatter(int k, int maxRow) {
117        ++maxRow; // To make it inclusive end index
118        if (segmentTree.querySum(1, 1, maxRow) < k) {
119            return false;
120        }
121        for (int row = 1; row <= rowCount; ++row) {
122            long seatsAvailable = segmentTree.querySum(1, row, row);
123            if (seatsAvailable >= k) {
124                segmentTree.modify(1, row, seatsAvailable - k);
125                return true;
126            }
127            k -= seatsAvailable;
128            segmentTree.modify(1, row, 0);
129        }
130        return true;
131    }
132}
133
1#include <vector>
2#include <algorithm>
3
4using namespace std;
5
6// Creating a class to represent a segment tree node.
7class SegmentTreeNode {
8public:
9    int left, right;
10    long sum, max;
11
12    SegmentTreeNode() : left(0), right(0), sum(0), max(0) {}
13};
14
15// Creating a class to handle segment tree operations.
16class SegmentTree {
17public:
18    // Initializing the segment tree with given number of rows and seats per row.
19    SegmentTree(int n, int m) : m(m) {
20        treeNodes.resize(n << 2);
21        for (int i = 0; i < (n << 2); ++i) {
22            treeNodes[i] = new SegmentTreeNode();
23        }
24        build(1, 1, n);
25    }
26  
27    ~SegmentTree() {
28        for (auto node : treeNodes) {
29            delete node;
30        }
31    }
32
33    // Modify the value for a single node (seat booking/cancellation).
34    void modify(int nodeIndex, int rowIndex, int value) {
35        if (treeNodes[nodeIndex]->left == rowIndex && treeNodes[nodeIndex]->right == rowIndex) {
36            treeNodes[nodeIndex]->sum = treeNodes[nodeIndex]->max = value;
37            return;
38        }
39        int mid = (treeNodes[nodeIndex]->left + treeNodes[nodeIndex]->right) >> 1;
40        if (rowIndex <= mid) {
41            modify(nodeIndex << 1, rowIndex, value);
42        } else {
43            modify(nodeIndex << 1 | 1, rowIndex, value);
44        }
45        pushUp(nodeIndex);
46    }
47
48    // Query the segment tree for the sum of a given range.
49    long querySum(int nodeIndex, int left, int right) {
50        if (treeNodes[nodeIndex]->left >= left && treeNodes[nodeIndex]->right <= right) {
51            return treeNodes[nodeIndex]->sum;
52        }
53        int mid = (treeNodes[nodeIndex]->left + treeNodes[nodeIndex]->right) >> 1;
54        long val = 0;
55        if (left <= mid) {
56            val += querySum(nodeIndex << 1, left, right);
57        }
58        if (right > mid) {
59            val += querySum(nodeIndex << 1 | 1, left, right);
60        }
61        return val;
62    }
63
64    // Query the segment tree for the row index with enough available seats.
65    int queryIndexWithEnoughSeats(int nodeIndex, int left, int right, int seatsRequired) {
66        if (treeNodes[nodeIndex]->max < seatsRequired) {
67            return 0;
68        }
69        if (treeNodes[nodeIndex]->left == treeNodes[nodeIndex]->right) {
70            return treeNodes[nodeIndex]->left;
71        }
72        int mid = (treeNodes[nodeIndex]->left + treeNodes[nodeIndex]->right) >> 1;
73        if (treeNodes[nodeIndex << 1]->max >= seatsRequired) {
74            return queryIndexWithEnoughSeats(nodeIndex << 1, left, right, seatsRequired);
75        }
76        if (right > mid) {
77            return queryIndexWithEnoughSeats(nodeIndex << 1 | 1, left, right, seatsRequired);
78        }
79        return 0;
80    }
81
82private:
83    vector<SegmentTreeNode*> treeNodes;
84    int m;
85
86    // Recursive method to build the segment tree.
87    void build(int nodeIndex, int left, int right) {
88        treeNodes[nodeIndex]->left = left;
89        treeNodes[nodeIndex]->right = right;
90        if (left == right) {
91            treeNodes[nodeIndex]->sum = m;
92            treeNodes[nodeIndex]->max = m;
93            return;
94        }
95        int mid = (left + right) >> 1;
96        build(nodeIndex << 1, left, mid);
97        build(nodeIndex << 1 | 1, mid + 1, right);
98        pushUp(nodeIndex);
99    }
100
101    // Method to update a node after modification.
102    void pushUp(int nodeIndex) {
103        treeNodes[nodeIndex]->sum = treeNodes[nodeIndex << 1]->sum + treeNodes[nodeIndex << 1 | 1]->sum;
104        treeNodes[nodeIndex]->max = max(treeNodes[nodeIndex << 1]->max, treeNodes[nodeIndex << 1 | 1]->max);
105    }
106};
107
108class BookMyShow {
109public:
110    // Constructor initializes a segment tree with n rows and m seats per row.
111    BookMyShow(int n, int m) : n(n), m(m) {
112        tree = new SegmentTree(n, m);
113    }
114  
115    ~BookMyShow() {
116        delete tree;
117    }
118
119    // Method to handle a gather operation to find and book contiguous seats.
120    vector<int> gather(int k, int maxRow) {
121        ++maxRow;
122        int rowIndex = tree->queryIndexWithEnoughSeats(1, 1, maxRow, k);
123        if (rowIndex == 0) {
124            return {}; // No sufficient seats found in any row up to maxRow.
125        }
126        long seatsOccupied = tree->querySum(1, rowIndex, rowIndex);
127        tree->modify(1, rowIndex, seatsOccupied - k);
128        return {rowIndex - 1, (int)(m - seatsOccupied)};
129    }
130
131    // Method to handle a scatter operation to book seats in a scattered manner.
132    bool scatter(int k, int maxRow) {
133        ++maxRow;
134        if (tree->querySum(1, 1, maxRow) < k) {
135            return false; // Insufficient seats available.
136        }
137        for (int rowIndex = 1; rowIndex <= maxRow; ++rowIndex) {
138            long seatsOccupied = tree->querySum(1, rowIndex, rowIndex);
139            if (seatsOccupied >= k) {
140                tree->modify(1, rowIndex, seatsOccupied - k);
141                return true;
142            }
143            k -= seatsOccupied;
144            tree->modify(1, rowIndex, 0);
145        }
146        return true;
147    }
148
149private:
150    SegmentTree* tree;
151    int m, n;
152};
153
1// Define a class to represent a segment tree node.
2class SegmentTreeNode {
3    public left: number;
4    public right: number;
5    public sum: number;
6    public max: number;
7
8    constructor() {
9        this.left = 0;
10        this.right = 0;
11        this.sum = 0;
12        this.max = 0;
13    }
14}
15
16// Global array to hold segment tree nodes.
17const treeNodes: SegmentTreeNode[] = [];
18let seatsPerRow: number;
19
20// Recursive function to build the segment tree.
21function build(nodeIndex: number, left: number, right: number): void {
22    treeNodes[nodeIndex] = new SegmentTreeNode();
23    treeNodes[nodeIndex].left = left;
24    treeNodes[nodeIndex].right = right;
25    if (left === right) {
26        treeNodes[nodeIndex].sum = seatsPerRow;
27        treeNodes[nodeIndex].max = seatsPerRow;
28        return;
29    }
30    let mid = (left + right) >> 1;
31    build(nodeIndex << 1, left, mid);
32    build(nodeIndex << 1 | 1, mid + 1, right);
33    pushUp(nodeIndex);
34}
35
36// Function to update a node after modification.
37function pushUp(nodeIndex: number): void {
38    treeNodes[nodeIndex].sum = treeNodes[nodeIndex << 1].sum + treeNodes[nodeIndex << 1 | 1].sum;
39    treeNodes[nodeIndex].max = Math.max(treeNodes[nodeIndex << 1].max, treeNodes[nodeIndex << 1 | 1].max);
40}
41
42// Function to modify the value for a single node (seat booking/cancellation).
43function modify(nodeIndex: number, rowIndex: number, value: number): void {
44    if (treeNodes[nodeIndex].left === rowIndex && treeNodes[nodeIndex].right === rowIndex) {
45        treeNodes[nodeIndex].sum = treeNodes[nodeIndex].max = value;
46        return;
47    }
48    let mid = (treeNodes[nodeIndex].left + treeNodes[nodeIndex].right) >> 1;
49    if (rowIndex <= mid) {
50        modify(nodeIndex << 1, rowIndex, value);
51    } else {
52        modify(nodeIndex << 1 | 1, rowIndex, value);
53    }
54    pushUp(nodeIndex);
55}
56
57// Function to query the segment tree for the sum of a given range.
58function querySum(nodeIndex: number, left: number, right: number): number {
59    if (treeNodes[nodeIndex].left >= left && treeNodes[nodeIndex].right <= right) {
60        return treeNodes[nodeIndex].sum;
61    }
62    let mid = (treeNodes[nodeIndex].left + treeNodes[nodeIndex].right) >> 1;
63    let val = 0;
64    if (left <= mid) {
65        val += querySum(nodeIndex << 1, left, right);
66    }
67    if (right > mid) {
68        val += querySum(nodeIndex << 1 | 1, left, right);
69    }
70    return val;
71}
72
73// Function to query the segment tree for the row index with enough available seats.
74function queryIndexWithEnoughSeats(nodeIndex: number, left: number, right: number, seatsRequired: number): number {
75    if (treeNodes[nodeIndex].max < seatsRequired) {
76        return 0;
77    }
78    if (treeNodes[nodeIndex].left === treeNodes[nodeIndex].right) {
79        return treeNodes[nodeIndex].left;
80    }
81    let mid = (treeNodes[nodeIndex].left + treeNodes[nodeIndex].right) >> 1;
82    if (treeNodes[nodeIndex << 1].max >= seatsRequired) {
83        return queryIndexWithEnoughSeats(nodeIndex << 1, left, right, seatsRequired);
84    }
85    if (right > mid) {
86        return queryIndexWithEnoughSeats(nodeIndex << 1 | 1, left, right, seatsRequired);
87    }
88    return 0;
89}
90
91// Starting point to initialize the segment tree. Call this function with the number of rows 'n' and seats per row 'm'.
92function initializeSegmentTree(n: number, m: number): void {
93    seatsPerRow = m;
94    build(1, 1, n);
95}
96
97// Wrapper function for the gather operation. Searches for and books a contiguous block of 'k' seats up to 'maxRow'.
98function gather(k: number, maxRow: number): [number, number] | [] {
99    maxRow++;
100    let rowIndex = queryIndexWithEnoughSeats(1, 1, maxRow, k);
101    if (rowIndex === 0) {
102        return []; // No sufficient seats found within the desired rows.
103    }
104    let seatsOccupied = querySum(1, rowIndex, rowIndex);
105    modify(1, rowIndex, seatsOccupied - k);
106    return [rowIndex - 1, seatsPerRow - seatsOccupied];
107}
108
109// Wrapper function for the scatter operation. Books individual seats totaling 'k' across different rows, up to 'maxRow'.
110function scatter(k: number, maxRow: number): boolean {
111    maxRow++;
112    if (querySum(1, 1, maxRow) < k) {
113        return false; // Not enough seats to fulfill the booking.
114    }
115    for (let rowIndex = 1; rowIndex <= maxRow; rowIndex++) {
116        let seatsOccupied = querySum(1, rowIndex, rowIndex);
117        if (seatsOccupied >= k) {
118            modify(1, rowIndex, seatsOccupied - k);
119            return true;
120        }
121        k -= seatsOccupied;
122        modify(1, rowIndex, 0);
123    }
124    return true;
125}
126

Time and Space Complexity

Time Complexity

  • SegmentTree build process: O(n) where n is the number of nodes, because it's a recursive call that initializes each node of the segment tree once.

  • SegmentTree modify operation: O(log n) because it takes a path from the root to a leaf node, where it updates a single node and all of its ancestors.

  • SegmentTree query_sum operation: O(log n) in the worst case, because it might traverse from the root to the deepest level of the tree, visiting two children at each level.

  • SegmentTree query_idx operation: O(log n) in the worst case, similar to query_sum, it traverses the segment tree to find the index with a value not less than k.

  • SegmentTree pushup helper function: O(1) because it only performs a constant amount of work to update the parent node based on its children.

  • BookMyShow gather method: O(log n) because it calls query_idx, query_sum, and modify, all of which are O(log n), once for a single operation.

  • BookMyShow scatter method: O(n log n) in the worst case, because in the worst-case scenario, it will iterate through all rows (O(n)) and for each row, calls query_sum and modify, each being O(log n).

Space Complexity

  • Overall Space Complexity: O(n), which is required to store the segment tree, where n is the number of nodes in the tree, which corresponds to 4 times the number of elements (rows) due to the nature of segment trees being full binary trees.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

Which of the following is a good use case for backtracking?

Recommended Readings

Segment Tree

Segment Tree Faster Range Queries For this article we want to introduce the idea of a Segment Tree Segment Trees allow us to quickly perform range queries as well as range updates Suppose we have an array and we want to know the sum of a particular range of numbers as well

Binary Search Speedrun

Binary Search Speedrun For each of the Speedrun questions you will be given a binary search related problem and a corresponding multiple choice question The multiple choice questions are related to the techniques and template s introduced in the binary search section It's recommended that you have gone through at

LeetCode Patterns: The Smart, Data-Driven Way to Prepare for Tech Interviews

LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More