Problem Description

The "Cinema Seat Allocation" problem asks you to determine the maximum number of 4-person families that can be seated in a cinema, given certain seat reservations.

The cinema has n rows, each with 10 seats labeled from 1 to 10. Some seats are already reserved and cannot be used. A family of 4 can be seated together if they occupy four consecutive seats in the same row, and their block of seats must be one of these three possible blocks:

• Seats 2, 3, 4, 5 (left block)
• Seats 4, 5, 6, 7 (middle block)
• Seats 6, 7, 8, 9 (right block)

• n: total number of rows
• reservedSeats: a list of reserved seat positions, where each reservation is a pair [row, seatNumber]

• Each family must occupy 4 consecutive seats in a single row.
• No two families can overlap or use the same seat.
• Some rows may have no reservations.

Thought Process

To solve this problem, let's start by considering the brute-force approach: for every row, check every possible block of 4 consecutive seats and see if it is available. Since there are only three valid blocks per row, this is manageable.

However, with potentially up to 10⁹ rows, iterating through every seat in every row would be too slow. The key observation is that only rows with reserved seats affect the answer, because in unreserved rows, both the left and right blocks are guaranteed to be available, and thus two families can always be seated.

So, we shift our focus to:

• Efficiently tracking which seats are reserved in each row.
• For each row with reservations, determine which of the three family blocks are available.
• For rows with no reservations, simply add two families per row.

Solution Approach

Here’s a step-by-step breakdown of the optimized algorithm:

1. Group reserved seats by row:
   • Use a hash map where the key is the row number and the value is a set of reserved seat numbers for that row.
2. Iterate through each row with reservations:
   • For each such row, check the availability of the three possible family blocks (left, middle, right).
   • A block is available if none of its seats are reserved in that row.
3. Count the maximum number of families per row:
   • If both left and right blocks are available, two families can be seated.
   • If only one or the middle block is available, one family can be seated.
   • If none are available, zero families can be seated in that row.
4. Handle rows with no reservations:
   • For all other rows (not in the hash map), both left and right blocks are available, so two families can be seated per row.
5. Sum results:
   • Add up the number of families from all rows to get the answer.

Example Walkthrough

Example Input:
n = 3
reservedSeats = [[1,2],[1,3],[1,8],[2,6],[3,1],[3,10]]

Step-by-step:

1. Group reserved seats:
   • Row 1: [2, 3, 8]
   • Row 2: [6]
   • Row 3: [1, 10]
2. Row 1:
   • Left block (2-5): seats 2 and 3 are reserved, so not available.
   • Middle block (4-7): all seats are free, so available.
   • Right block (6-9): seat 8 is reserved, so not available.
   • Result: Only the middle block is available → 1 family.
3. Row 2:
   • Left block: seats 2-5 are free.
   • Middle block: seat 6 is reserved.
   • Right block: seat 6 is reserved.
   • Result: Only the left block is available → 1 family.
4. Row 3:
   • Row 3 reservations are at seats 1 and 10, which don't affect any block.
   • Both left and right blocks are available → 2 families.
5. Sum: 1 (row 1) + 1 (row 2) + 2 (row 3) = 4 families

Time and Space Complexity

Brute-force approach:

• Time: O(n) per row × 3 blocks per row × 4 seats per block = O(n)
• Space: O(n) to store reservations
• But with large n, this is not efficient.

• Time: O(k), where k is the number of reserved seats. We only process rows with reservations.
• Space: O(k), to store reservations by row.
• Why? Because we only check rows with reservations; all others are handled in O(1) per row.

Summary

The "Cinema Seat Allocation" problem is solved efficiently by focusing only on rows with reserved seats and determining which family blocks remain available. By using a hash map to group reservations per row, we avoid unnecessary checks and achieve optimal performance even for large numbers of rows. The solution elegantly combines simple block checks with efficient data structures for a fast and clear result.

Code Implementation

class Solution:
    def maxNumberOfFamilies(self, n, reservedSeats):
        from collections import defaultdict
        reserved = defaultdict(set)
        for row, seat in reservedSeats:
            reserved[row].add(seat)
        ans = 0
        for row in reserved:
            seats = reserved[row]
            left = all(s not in seats for s in [2,3,4,5])
            right = all(s not in seats for s in [6,7,8,9])
            middle = all(s not in seats for s in [4,5,6,7])
            if left and right:
                ans += 2
            elif left or right or middle:
                ans += 1
        ans += 2 * (n - len(reserved))
        return ans
      

class Solution {
public:
    int maxNumberOfFamilies(int n, vector<vector<int>>& reservedSeats) {
        unordered_map<int, unordered_set<int>> reserved;
        for (auto &seat : reservedSeats) {
            reserved[seat[0]].insert(seat[1]);
        }
        int ans = 0;
        for (auto &kv : reserved) {
            auto &seats = kv.second;
            bool left = true, right = true, middle = true;
            for (int s : {2,3,4,5}) if (seats.count(s)) left = false;
            for (int s : {6,7,8,9}) if (seats.count(s)) right = false;
            for (int s : {4,5,6,7}) if (seats.count(s)) middle = false;
            if (left && right)
                ans += 2;
            else if (left || right || middle)
                ans += 1;
        }
        ans += 2 * (n - reserved.size());
        return ans;
    }
};
      

import java.util.*;

class Solution {
    public int maxNumberOfFamilies(int n, int[][] reservedSeats) {
        Map<Integer, Set<Integer>> reserved = new HashMap<>();
        for (int[] seat : reservedSeats) {
            reserved.computeIfAbsent(seat[0], k -> new HashSet<>()).add(seat[1]);
        }
        int ans = 0;
        for (Set<Integer> seats : reserved.values()) {
            boolean left = true, right = true, middle = true;
            for (int s : new int[]{2,3,4,5}) if (seats.contains(s)) left = false;
            for (int s : new int[]{6,7,8,9}) if (seats.contains(s)) right = false;
            for (int s : new int[]{4,5,6,7}) if (seats.contains(s)) middle = false;
            if (left && right)
                ans += 2;
            else if (left || right || middle)
                ans += 1;
        }
        ans += 2 * (n - reserved.size());
        return ans;
    }
}
      

var maxNumberOfFamilies = function(n, reservedSeats) {
    const reserved = new Map();
    for (const [row, seat] of reservedSeats) {
        if (!reserved.has(row)) reserved.set(row, new Set());
        reserved.get(row).add(seat);
    }
    let ans = 0;
    for (const seats of reserved.values()) {
        let left = [2,3,4,5].every(s => !seats.has(s));
        let right = [6,7,8,9].every(s => !seats.has(s));
        let middle = [4,5,6,7].every(s => !seats.has(s));
        if (left && right) ans += 2;
        else if (left || right || middle) ans += 1;
    }
    ans += 2 * (n - reserved.size);
    return ans;
};