Watch 10 video solutions for Cinema Seat Allocation, a medium level problem involving Array, Hash Table, Greedy. This walkthrough by Coding Interviews has 5,707 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
A cinema has n rows of seats, numbered from 1 to n and there are ten seats in each row, labelled from 1 to 10 as shown in the figure above.
Given the array reservedSeats containing the numbers of seats already reserved, for example, reservedSeats[i] = [3,8] means the seat located in row 3 and labelled with 8 is already reserved.
Return the maximum number of four-person groups you can assign on the cinema seats. A four-person group occupies four adjacent seats in one single row. Seats across an aisle (such as [3,3] and [3,4]) are not considered to be adjacent, but there is an exceptional case on which an aisle split a four-person group, in that case, the aisle split a four-person group in the middle, which means to have two people on each side.
Example 1:
Input: n = 3, reservedSeats = [[1,2],[1,3],[1,8],[2,6],[3,1],[3,10]] Output: 4 Explanation: The figure above shows the optimal allocation for four groups, where seats mark with blue are already reserved and contiguous seats mark with orange are for one group.
Example 2:
Input: n = 2, reservedSeats = [[2,1],[1,8],[2,6]] Output: 2
Example 3:
Input: n = 4, reservedSeats = [[4,3],[1,4],[4,6],[1,7]] Output: 4
Constraints:
1 <= n <= 10^91 <= reservedSeats.length <= min(10*n, 10^4)reservedSeats[i].length == 21 <= reservedSeats[i][0] <= n1 <= reservedSeats[i][1] <= 10reservedSeats[i] are distinct.Problem Overview: A cinema has n rows with 10 seats per row. Some seats are already reserved. A family of four must sit together in one of three valid blocks: [2,3,4,5], [4,5,6,7], or [6,7,8,9]. The task is to compute the maximum number of families that can be seated without breaking these constraints.
The key observation: each row can normally hold two families (left block 2-5 and right block 6-9). Reserved seats only affect the rows where they appear, so you never need to simulate all n rows when n can be as large as 1e9. Instead, track only rows that contain reservations using a hash table.
Approach 1: Greedy Approach Using Logical Checks (O(r) time, O(r) space)
Group reserved seats by row using a map. For each affected row, check whether the three valid family blocks are free. Use simple logical checks to see if seats in ranges 2-5, 4-7, or 6-9 contain any reservation. If both left and right blocks are free, place two families. Otherwise check if the middle block 4-7 is free and place one family if possible. Rows without reservations automatically contribute two families. This approach relies on direct seat checks with an array or set lookup and works well because each row has only a constant number of seat groups to evaluate.
Approach 2: Bitmask Representation for Each Row (O(r) time, O(r) space)
Instead of storing seat numbers directly, encode reserved seats for each row as a bitmask. Each bit represents whether a seat from 2 to 9 is occupied. Bitwise AND operations quickly test whether a candidate family block conflicts with reservations. Precompute masks for the three valid seat groups (2-5, 4-7, 6-9). For each row mask, check conflicts using bit operations like (mask & groupMask) == 0. Bitmasks make the checks extremely fast and compact, which is why this solution often appears in competitive programming and bit manipulation interview problems.
Recommended for interviews: The greedy row-by-row check is usually the first solution interviewers expect because it clearly models the seating rules. The bitmask version demonstrates deeper optimization and familiarity with low-level operations. Both achieve O(r) time where r is the number of reserved seats (or rows containing reservations), which is optimal since only those rows need processing.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy Logical Seat Checks | O(r) | O(r) | Best for readability and interviews when you want a clear rule-based solution |
| Bitmask Representation per Row | O(r) | O(r) | Preferred when optimizing seat checks with fast bit operations |