Cinema Seat Allocation: Greedy Group Placement

LeetCode 1386, Cinema Seat Allocation, gives you a cinema with n rows of 10 seats each and a list of reservedSeats pairs [row, seat]. Your task is to maximize the number of groups of four people that can be seated. Each group must occupy four consecutive seats in one of three fixed positions: seats 2-5, seats 4-7, or seats 6-9. A single row can hold at most two non-overlapping groups. Return the maximum number of groups you can place across all rows.

Why this problem matters

Cinema Seat Allocation is a clean example of the greedy pattern applied to constrained placement. You do not need dynamic programming or backtracking. The constraint space is tiny (only three possible group positions per row), which means you can check every option directly. The real challenge is handling the scale: n can be up to 10^9 rows, so you cannot iterate over every row. You must focus only on the rows that have reservations.

The key insight

Each row has exactly three possible group placements: seats 2-5 (left), seats 4-7 (middle), and seats 6-9 (right). The left and right groups do not overlap, so one row can hold at most two groups. The middle group overlaps with both left and right, so if you place the middle group, you cannot place either of the others.

For each row with reservations, you check which of the three positions are blocked. If both left and right are free, you place two groups. If only left or only right is free, you place one. If neither is free but the middle is, you still place one. Otherwise, zero.

Rows without any reservations always contribute two groups (left and right). Since n can be huge, you only process the rows that appear in reservedSeats and add 2 * (n - rows_with_reservations) for the rest.

The solution

def max_number_of_families(n, reservedSeats):
    from collections import defaultdict
    row_map = defaultdict(set)
    for r, s in reservedSeats:
        row_map[r].add(s)

    count = 0
    for reserved in row_map.values():
        left = all(s not in reserved for s in (2, 3, 4, 5))
        right = all(s not in reserved for s in (6, 7, 8, 9))
        middle = all(s not in reserved for s in (4, 5, 6, 7))

        if left and right:
            count += 2
        elif left or right or middle:
            count += 1

    count += 2 * (n - len(row_map))
    return count

The function groups reservations by row using a hash map. For each row that has at least one reserved seat, it checks the three group positions. The all(...) call returns True when none of the seats in that range are reserved. If both the left and right positions are free, you get two groups. If only one of the three positions is free, you get one. Rows with no reservations at all are never stored in the map, so you add 2 * (n - len(row_map)) at the end.

Visual walkthrough

The walkthrough shows the core logic: group reserved seats by row, check the three fixed positions, and count how many fit. Rows without reservations skip this check entirely and contribute 2 groups each.

Complexity analysis

Here r is the number of reserved seats (the length of the reservedSeats array). Building the hash map takes O(r) time. Iterating over the map visits at most r rows (one entry per row that has reservations). Each row check is O(1) because you only test fixed seat numbers. Space is O(r) for the hash map storing reserved seats.

The solution does not depend on n at all (except for the final multiplication), which is critical when n can be up to 10^9.

The building blocks

1. Group reserved seats by row

The first step is organizing the input. A defaultdict(set) maps each row number to the set of reserved seat numbers in that row.

row_map = defaultdict(set)
for r, s in reservedSeats:
    row_map[r].add(s)

This lets you look up any row's reservations in O(1). Using a set makes the membership check s not in reserved constant time.

2. Check fixed group placements

For each row, you check three hardcoded seat ranges against the reserved set:

left = all(s not in reserved for s in (2, 3, 4, 5))
right = all(s not in reserved for s in (6, 7, 8, 9))
middle = all(s not in reserved for s in (4, 5, 6, 7))

if left and right:
    count += 2
elif left or right or middle:
    count += 1

The order matters. You check left and right first because that yields two groups. Only if that fails do you check whether any single group fits. The middle group is a fallback: if left is blocked and right is blocked, maybe the middle still works.

Edge cases

• No reservations at all. The row_map is empty, so the loop body never runs. The answer is 2 * n.
• Every seat in a row is reserved. No group fits that row. It contributes 0.
• Only seat 1 or seat 10 is reserved. These seats are never part of any group (groups use seats 2-9). The row still contributes 2 groups.
• Reservations in seats 4 and 5 only. Both left (seats 2-5) and middle (seats 4-7) are blocked, but right (seats 6-9) is free. The row contributes 1 group.
• Single row, n = 1. Works the same way. Process the one row and return the count.
• Very large n with few reservations. The hash map is small, and the unreserved rows are handled by the multiplication. No performance issue.

From understanding to recall

The logic is simple once you see it: three fixed positions, check each one, count what fits. But under interview pressure, the details trip people up. Do you check left and right first or left or right or middle? Do you remember that the middle group overlaps both sides? Do you remember to add 2 * (n - len(row_map)) for unreserved rows?

These are small points that are easy to forget if you have only read the solution once. The way to lock it in is to practice writing the hash-map grouping and the three-position check from scratch. After a few rounds of spaced repetition, the pattern becomes automatic, and you can reproduce it without hesitation.

Related posts

• Meeting Rooms II - Scheduling with overlapping intervals and greedy allocation
• Non-overlapping Intervals - Greedy removal to eliminate overlaps in interval sets
• Insert Interval - Merging a new interval into a sorted list with a three-phase scan

CodeBricks breaks Cinema Seat Allocation into its hash-map grouping and greedy placement building blocks, then drills them with spaced repetition. You type each piece from scratch until the pattern is automatic. When a constrained placement question shows up in your interview, you do not think about it. You just write it.