Booking Concert Tickets in Groups

Booking Concert Tickets in Groups

What is this problem about?

This "Hard" coding problem asks you to design a system for booking concert tickets. You have $n$ rows, each with $m$ seats. You need to implement two operations:

1. gather: Find the first row that has enough consecutive free seats for a group.
2. scatter: Fill the available seats across multiple rows starting from the first possible row. The system needs to handle a large number of rows and queries efficiently.

Why is this asked in interviews?

Google uses this problem to test advanced system design and data structure implementation skills. It requires more than just an array; you need a way to quickly find the minimum seat index and the total sum of available seats. It's a perfect test for a Segment Tree because you need to query both the "maximum available consecutive seats" and the "sum of available seats" over a range of rows.

Algorithmic pattern used

The primary pattern is the Segment Tree. Each node in the tree stores two values: the maximum number of seats available in any single row in that range, and the total number of free seats in that range. This allows you to perform gather (using the max value to find a suitable row) and scatter (using the sum to see if enough seats exist) in $O(\log N)$ time.

Example explanation

Rows: 3, Seats per row: 5.

1. gather(2, 2): Can we fit 2 people in a single row within the first 2 rows? Row 0 has 5 seats. Yes. Result: [0, 0] (Row 0, starts at seat 0). Row 0 now has 3 seats left.
2. scatter(8, 2): Can we fit 8 people across the first 2 rows? Row 0 has 3, Row 1 has 5. Total = 8. Yes. Seats are filled. Both Row 0 and Row 1 are now empty.
3. gather(2, 2): Row 0 and 1 are full. Max available in Row 2 is 5. Row 2 can take them. Result: [2, 0].

Common mistakes candidates make

A common pitfall is attempting to use a simple array or a heap. A heap can help find the maximum, but it doesn't help with the "scatter" operation where you need to fill rows in order. Another mistake is forgetting that gather only looks for consecutive seats in a single row, while scatter can span multiple rows. The most significant challenge is correctly updating the segment tree after a scatter operation, as it can affect multiple rows.

Interview preparation tip

This is a very advanced problem. To prepare, you should be extremely comfortable with Segment Trees. Understand how to store multiple types of metadata (like max and sum) in a single tree. Also, practice the "binary search on segment tree" technique, which is used here to find the first row that satisfies the gather condition.