Cinema Seat Allocation
Asked at Meta
Problem
A cinema has n rows of 10 seats each, labeled 1 through 10. Some seats are already reserved. Four-person groups want to sit together in the same row, occupying four consecutive empty seats. Count the maximum number of families that can be seated across all rows.
Asked At
| Company | Difficulty | |
|---|---|---|
| Meta | Medium | View all Meta questions → |
How to Think About It
Brute force per row: for each of the n rows, test the left group (seats 2-5), right group (6-9), and middle group (4-7). A row with no reservations fits two families (left + right). Time O(n * 10).
Key insight: only rows that appear in the reservations list need inspection. Every other row fits 2 families automatically. Store reservations as a hash map from row number to the set of reserved seats in that row.
Middle group (4,5,6,7) matters only when left AND right are both blocked. A row with reservations seats at most 1 family unless both left and right are free (no overlap with middle). Check left first, then right, then middle as fallback.
Visual walkthrough for row with reservations {5,6}: left (2,3,4,5) blocked by 5. right (6,7,8,9) blocked by 6. middle (4,5,6,7) blocked by 5. Score: 0 families. Another row with {1,10}: left free, right free. Score: 2 families.
The formula: if left free AND right free -> 2. Else if left free OR right free OR middle free -> 1. Else 0. Rows not in the reservation map get 2 automatically.
Edge cases: n can be up to 10^9 (very large), so you cannot iterate all rows. Only iterate rows that appear in reservations. The answer is 2 * (n - number of reserved rows) + sum of per-row scores.
Optimal Approach
Step 1: Build a hash map from row number to the set of reserved seats in that row.
Step 2: Initialize answer = 2 * (n - number of rows in the map). This accounts for all rows with no reservations.
Step 3: For each row in the map, compute the family count:
- Check left group (seats 2,3,4,5): if none reserved, left_count = 1
- Check right group (seats 6,7,8,9): if none reserved, right_count = 1
- If left_count + right_count == 0, check middle (4,5,6,7): if none reserved, add 1
- Otherwise add left_count + right_count
Step 4: Return the total.
Walkthrough with n=3, reservedSeats=[[1,2],[1,3],[1,8],[2,6],[3,1],[3,10]]:
- Row 1: reserved {2,3,8}. Left blocked (2,3 taken). Right: 8 taken -> blocked. Middle: 4,5,6,7 free? 4,5,6,7 none in {2,3,8} -> middle free. Score: 1.
- Row 2: reserved {6}. Left free (2,3,4,5). Right: 6 taken -> blocked. Score: 1 (left only).
- Row 3: reserved {1,10}. Left free. Right free. Score: 2.
- Rows with no reservations: 3 - 3 = 0.
- Total: 1 + 1 + 2 = 4.
Time: O(R) where R is the number of reserved seats. Space: O(R) for the hash map.
What Trips People Up in Real Interviews
Iterating all n rows when n can be 10^9. Only rows in the reservations map need per-row logic. Use 2 * (n - len(reserved_rows)) for the rest.
Forgetting that a row with no reservations seats 2 families, not 1. Left (2-5) and right (6-9) are disjoint and both fit simultaneously.
Checking middle group when left or right is already free. Middle overlaps both, so it never adds beyond what left+right provide. Use middle only as a fallback when both left and right are blocked.
Confusing seat numbers. Seats are 1-indexed: left = {2,3,4,5}, right = {6,7,8,9}, middle = {4,5,6,7}. Seat 1 and 10 are never used by any family group.
Missing that the same row can appear multiple times in reservedSeats. Use a set per row to deduplicate before checking groups.
Solution Code
def maxNumberOfFamilies(n, reservedSeats):
rows = {}
for r, s in reservedSeats:
rows.setdefault(r, set()).add(s)
ans = 2 * (n - len(rows))
for seats in rows.values():
left = not ({2,3,4,5} & seats)
right = not ({6,7,8,9} & seats)
middle = not ({4,5,6,7} & seats)
if left and right:
ans += 2
elif left or right or middle:
ans += 1
return ansFrequently Asked Questions
What is the Cinema Seat Allocation problem?
A cinema has n rows of 10 seats each, labeled 1 through 10. Some seats are already reserved. Four-person groups want to sit together in the same row, occupying four consecutive empty seats. Count the maximum number of families that can be seated across all rows.
How do you solve Cinema Seat Allocation?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Cinema Seat Allocation?
Cinema Seat Allocation is asked at Meta. It is a medium difficulty problem.
What are common mistakes on Cinema Seat Allocation?
- Iterating all n rows when n can be 10^9. Only rows in the reservations map need per-row logic. Use `2 * (n - len(reserved_rows))` for the rest.
- Forgetting that a row with no reservations seats 2 families, not 1. Left (2-5) and right (6-9) are disjoint and both fit simultaneously.
- Checking middle group when left or right is already free. Middle overlaps both, so it never adds beyond what left+right provide. Use middle only as a fallback when both left and right are blocked.
- Confusing seat numbers. Seats are 1-indexed: left = {2,3,4,5}, right = {6,7,8,9}, middle = {4,5,6,7}. Seat 1 and 10 are never used by any family group.
- Missing that the same row can appear multiple times in reservedSeats. Use a set per row to deduplicate before checking groups.