{x}
blog image

Booking Concert Tickets in Groups

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.

Solution Explanation for LeetCode 2286: Booking Concert Tickets in Groups

This problem requires designing a system to book concert tickets, handling both group bookings where individuals must sit together and group bookings where individuals can be scattered. The system needs to efficiently find the best available seats, prioritizing lower row numbers and seat numbers. A Segment Tree is an ideal data structure for this task due to its efficient handling of range queries and updates.

Approach using Segment Tree

The core idea is to represent the available seats in each row using a segment tree. Each node in the segment tree represents a range of seats within a row. The node stores:

  • l, r: The start and end indices of the seat range represented by the node.
  • s: The total number of available seats within the range.
  • mx: The maximum number of consecutive available seats within the range.

Data Structures:

  • Node: A class to represent a node in the segment tree.
  • SegmentTree: A class to manage the segment tree, including building, updating (modify), and querying (querySum, queryIdx) operations.
  • BookMyShow: The main class implementing the ticketing system.

Operations:

  1. build(u, l, r): Recursively builds the segment tree. The leaf nodes represent individual seats, and the parent nodes represent ranges of seats.

  2. modify(u, x, v): Updates the number of available seats at index x to v. It propagates the changes up the tree.

  3. querySum(u, l, r): Returns the total number of available seats in the range [l, r].

  4. queryIdx(u, l, r, k): Finds the smallest row index where at least k consecutive seats are available. This is crucial for the gather operation. It utilizes binary search on the tree to efficiently locate the appropriate row.

  5. pushup(u): Updates the s and mx values of a node based on its children's values. This is called after any modification to ensure consistency.

  6. gather(k, maxRow): Finds and books k consecutive seats in rows up to maxRow. It uses queryIdx to find a suitable row and then modify to update the tree after booking.

  7. scatter(k, maxRow): Finds and books k seats, not necessarily consecutive, in rows up to maxRow. It iterates through rows, booking seats greedily from the lowest row numbers and smallest seat numbers until k seats are booked.

Time and Space Complexity

  • Time Complexity:

    • Initialization: O(n) to build the segment tree.
    • gather: O(log n) to find the row and book the seats.
    • scatter: O(n log n) in the worst case (iterating through all rows and performing log n operations per row for tree updates). However, in practice, it's often faster since it usually doesn't need to traverse all rows.

  • Space Complexity: O(n) to store the segment tree.

Code Examples (Python, Java, C++, Go, TypeScript)

The provided code in the different languages implements the BookMyShow class and the segment tree data structure as described above. Each language's code follows the same logic but with the syntax specific to the language. Refer to the code sections within the previous response for detailed implementations in each language.

The segment tree approach provides an efficient solution to this problem by handling range queries and updates effectively, allowing for quick seat allocation and booking. While the worst-case time complexity for scatter is O(n log n), its average-case performance is usually much better because of the greedy nature of the seat allocation.