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:
k spectators can sit together in a row.k spectators can get a seat. They may or may not sit together.Note that the spectators are very picky. Hence:
maxRow. maxRow can vary from group to group.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 * 1041 <= m, k <= 1090 <= maxRow <= n - 15 * 104 calls in total will be made to gather and scatter.Problem Overview: You need to design a ticket booking system for a concert hall with n rows and m seats per row. Two operations are supported: gather, which books k consecutive seats in a single row up to maxRow, and scatter, which books k seats across multiple rows (not necessarily consecutive) up to maxRow. The challenge is handling many queries efficiently while constantly updating available seats.
Approach 1: Brute Force with Linear Search (Time: O(n) per query, Space: O(n))
Maintain an array that stores how many seats remain in each row. For a gather request, iterate from row 0 to maxRow and check whether a row has at least k consecutive seats available. Once found, allocate seats and update the remaining capacity. For scatter, iterate through rows up to maxRow, filling seats greedily until k tickets are assigned. This approach is easy to implement and works well when the number of rows or queries is small. However, every request may scan many rows, making it inefficient when n and query count are large.
Approach 2: Binary Search with Prefix Sums (Time: O(log n) per query, Space: O(n))
Optimize the search process using prefix sums and binary search. Maintain cumulative seat availability so you can quickly determine how many seats exist in rows 0..maxRow. For scatter, check the prefix sum to confirm whether enough seats exist, then distribute seats across rows while updating the structure. For gather, binary search the earliest row that still has at least k consecutive seats. After allocation, update the prefix values to reflect the reduced capacity.
This design significantly reduces row scanning. Instead of checking every row, you locate candidate rows with logarithmic search and maintain running totals for fast validation. In large systems with thousands of rows and frequent operations, this difference is critical. Many implementations internally rely on structures similar to a segment tree or binary indexed tree to support these prefix queries and updates efficiently.
Recommended for interviews: Interviewers expect an optimized design rather than repeated linear scans. Starting with the brute force approach shows you understand the booking rules and constraints. The optimized binary-search/prefix-sum strategy demonstrates stronger algorithmic thinking and familiarity with scalable data structures used in real systems.
This approach involves iterating through each row to check if the required number of consecutive seats (for gather) or total seats (for scatter) are available. It's straightforward but can be inefficient for large inputs.
In this solution, we represent the concert hall using an array where each element contains the number of seats booked in the corresponding row. When using gather, we iterate through rows checking for available consecutive seats. For scatter, we distribute seats across rows until all are booked or no seats are left.
Time Complexity: O(n*m); Space Complexity: O(n), where n is the number of rows.
To enhance seat allocation efficiency, we utilize binary search combined with prefix sums. By preprocessing seat availability data, both gather and scatter operations can be executed in a more optimized manner.
This C solution augments the simple approach with a total seat counter. The scatter method exploits this counter to quickly invalidate requests exceeding total availability, thus optimizing seat watching operations.
Time Complexity: O(n + m); Space Complexity: O(n), where direct seat counting offsets redundant checks.
From the problem description, we can deduce the following:
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.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 intervalr: The right endpoint of the node's intervals: The total remaining seats in the interval corresponding to the nodemx: The maximum remaining seats in the interval corresponding to the nodeNote 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:
O(n).gather(k, maxRow) is O(log n).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.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Approach 1: Brute Force with Linear Search | Time Complexity: O(n*m); Space Complexity: O(n), where n is the number of rows. |
| Approach 2: Optimized with Binary Search and Prefix Sums | Time Complexity: O(n + m); Space Complexity: O(n), where direct seat counting offsets redundant checks. |
| Segment Tree | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force with Linear Search | O(n) per query | O(n) | Simple implementation when row count or query volume is small |
| Binary Search with Prefix Sums | O(log n) per query | O(n) | Large inputs with many queries where fast seat lookup and updates are required |
BiWeekly Contest 79 | 10011. Booking Concert Tickets in Groups • codingMohan • 6,083 views views
Watch 6 more video solutions →Practice Booking Concert Tickets in Groups with our built-in code editor and test cases.
Practice on FleetCode