Cinema Seat Allocation

Intuitionwhy only a few seat patterns matter

A row has room for at most two groups of four, because the usable seats for groups are seats 2 through 9. The only way to place two groups is to use the left block, seats 2 through 5, and the right block, seats 6 through 9. These blocks do not overlap. The middle block, seats 4 through 7, can provide one group, but it overlaps both outer blocks.

Most rows have no reservation that affects any allowed block, so they contribute two groups immediately. You only need to inspect rows containing a reservation in seats 2 through 9. For each such row, record which of those eight seats are occupied, test the three possible blocks, and add two if both outer blocks are free, one if any block is free, and zero otherwise.

Approach

1. 1Create a mask for each row that has a reservation in seats 2 through 9, mapping seat 2 to bit 0 and seat 9 to bit 7. Ignore seats 1 and 10 because neither can belong to an allowed four-seat block.
2. 2Start with two groups for every row not present in the map, adding 2 times n minus the number of affected rows. This handles the enormous number of untouched rows without iterating through all n rows.
3. 3For each relevant reservation, set its row's corresponding bit with bitwise OR. OR preserves earlier reservations and lets all seats in one row be represented by one integer.
4. 4Test the left, middle, and right block masks against the row mask. A block is free exactly when the bitwise AND is zero, because that means none of its four seat bits is reserved.
5. 5If both the left and right blocks are free, add two for that row. They are disjoint, so two groups really fit; checking all three free blocks independently would incorrectly count overlapping choices.
6. 6Otherwise, add one when at least one candidate block is free, and add zero when every candidate intersects a reservation. The middle block still matters in this branch because it may be the only usable option.
7. 7Return the accumulated total. Each affected row is processed once, while rows with no relevant reservations were already counted in bulk.

Complexitythe cost depends on reservations, not on the number of rows

Annotated solutionC++ · hash map plus one eight-bit mask per affected row

#include <unordered_map>
#include <vector>

using namespace std;

class Solution {
public:
    int maxNumberOfFamilies(int n, vector<vector<int>>& reservedSeats) {
        unordered_map<int, int> rowMask;

        for (const auto& seat : reservedSeats) {
            int row = seat[0];
            int column = seat[1];

            if (column >= 2 && column <= 9) {
                rowMask[row] |= 1 << (column - 2);
            }
        }

        int total = 2 * (n - static_cast<int>(rowMask.size()));

        for (const auto& entry : rowMask) {
            int mask = entry.second;

            bool left = (mask & 0b00001111) == 0;
            bool middle = (mask & 0b00111100) == 0;
            bool right = (mask & 0b11110000) == 0;

            if (left && right) {
                total += 2;
            } else if (left || middle || right) {
                total += 1;
            }
        }

        return total;
    }
};

The initial total is the key compression step: every row absent from rowMask has all three candidate blocks free and contributes exactly two. For an affected row, the mask tests do not need to know which reservation caused a conflict. They only answer whether every bit in a candidate block is zero, which is precisely the condition for placing a group.

Common mistakesthree wrong shapes that look plausible