341. Cinema Seat Allocation

Only seats 2-9 matter, and each row fits at most two groups. Any row with no reservation in 2-9 always seats two groups, so count those in bulk and only inspect the rows that actually appear in the reservations.

Key observations

Seats 1 and 10 can never be part of any four-person block (every block lives inside seats 2-9), so they are irrelevant. Inside a single row there are only three candidate blocks:

• left = seats 2, 3, 4, 5
• middle = seats 4, 5, 6, 7
• right = seats 6, 7, 8, 9

Because the left and right blocks don't overlap, a row can seat at most two groups (left + right). The middle block only helps when neither the pure-left nor pure-right block is fully free.

Why we ignore most rows

n can be up to 10^9, but at most 10^4 seats are reserved. A row with no reservation among seats 2-9 can always seat two groups. So every row that does not appear in reservedSeats contributes exactly 2. Start the answer at (n - affectedRows) * 2 and then only examine the handful of rows that were actually touched.

Deciding one row

Group the reservations by row into a bitmask mask (bit s set means seat s is taken). For that row:

1. left free ⇔ none of seats {2,3,4,5} set
2. middle free ⇔ none of seats {4,5,6,7} set
3. right free ⇔ none of seats {6,7,8,9} set

Then greedily:

• if left and right are both free → +2
• else if left or middle or right is free → +1
• otherwise → +0

Worked example

n = 3, reservedSeats = [[1,2],[1,3],[1,8],[2,6],[3,1],[3,10]].

All three rows appear in the input, so the bulk term is (3 - 3) * 2 = 0.

• Row 1 reserves {2,3,8}. left has 2,3 → blocked; right has 8 → blocked; but middle {4,5,6,7} is free → +1.
• Row 2 reserves {6}. left {2,3,4,5} is free → at least one group; right has 6 → blocked → +1.
• Row 3 reserves {1,10}. Seats 1 and 10 don't matter, so left and right are both free → +2.

Total = 0 + 1 + 1 + 2 = 4.

Complexity

• Time: O(R) where R = reservedSeats.length — one pass to build the masks, one pass over the affected rows.
• Space: O(D) for the distinct affected rows (at most R).

class Solution {
    public int maxNumberOfFamilies(int n, int[][] reservedSeats) {
        Map<Integer, Integer> rows = new HashMap<>();
        for (int[] rs : reservedSeats) {
            rows.merge(rs[0], 1 << rs[1], (a, b) -> a | b);
        }

        // Rows that appear in no reservation always seat two groups.
        long total = (long) (n - rows.size()) * 2;

        int left = (1 << 2) | (1 << 3) | (1 << 4) | (1 << 5);
        int middle = (1 << 4) | (1 << 5) | (1 << 6) | (1 << 7);
        int right = (1 << 6) | (1 << 7) | (1 << 8) | (1 << 9);

        for (int mask : rows.values()) {
            boolean leftFree = (mask & left) == 0;
            boolean middleFree = (mask & middle) == 0;
            boolean rightFree = (mask & right) == 0;
            if (leftFree && rightFree) {
                total += 2;
            } else if (leftFree || middleFree || rightFree) {
                total += 1;
            }
        }
        return (int) total;
    }
}