Booking Concert Tickets in Groups - Video Solutions
BiWeekly Contest 79 | 10011. Booking Concert Tickets in Groups
Booking Concert Tickets in Groups - Video Solution
Watch 6 video solutions for Booking Concert Tickets in Groups, a hard level problem involving Binary Search, Design, Binary Indexed Tree. This walkthrough by codingMohan has 6,279 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
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
kspectators can sit together in a row. - If every member of a group of
kspectators 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.maxRowcan 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 withnas number of rows andmas number of seats per row.int[] gather(int k, int maxRow)Returns an array of length2denoting the row and seat number (respectively) of the first seat being allocated to thekmembers of the group, who must sit together. In other words, it returns the smallest possiblerandcsuch that all[c, c + k - 1]seats are valid and empty in rowr, andr <= maxRow. Returns[]in case it is not possible to allocate seats to the group.boolean scatter(int k, int maxRow)Returnstrueif allkmembers of the group can be allocated seats in rows0tomaxRow, who may or may not sit together. If the seats can be allocated, it allocateskseats to the group with the smallest row numbers, and the smallest possible seat numbers in each row. Otherwise, returnsfalse.
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 - 1- At most
5 * 104calls in total will be made togatherandscatter.
Approach Overview
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.
Complexity Analysis
| 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 |