1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
    public int maxNumberOfFamilies(int n, int[][] reservedSeats) {
        int ans = 0;
        Map<Integer, Integer> reservedRow = new HashMap<>();
        for (int[] reservedSeat : reservedSeats) {
            reservedRow.put(reservedSeat[0] - 1,
                    reservedRow.getOrDefault(reservedSeat[0] - 1, 0) | (1 << (reservedSeat[1] - 1)));
        }
        for (int currRowSeatStatus : reservedRow.values()) {
            if (currRowSeatStatus == 0) {
                ans += 2;
                continue;
            }
            boolean leftFree = true, middleFree = true, rightFree = true;
            // 0 1 1 | 1 1 0 0 | 0 0 0
            if ((currRowSeatStatus & 0x1e) != 0)
                leftFree = false;
            // 0 0 0 | 1 1 1 1 | 0 0 0
            if ((currRowSeatStatus & 0x78) != 0)
                middleFree = false;
            // 0 0 0 | 0 0 1 1 | 1 1 0
            if ((currRowSeatStatus & 0x1e0) != 0)
                rightFree = false;
            if (leftFree && rightFree) {
                ans += 2;
            } else if (leftFree || rightFree || middleFree) {
                ans += 1;
            }
        }
        return ans + 2 * (n - reservedRow.size());
    }
}

我们用一个map记录哪些row的哪些位置被占用了. 因为每行只有10个座位, 我们只需要用一个integer表示一个row的座位占用情况即可. 之后我们遍历map中的row. 一个row出现4连座只有三种情况: 带左边过道, 带右边过道, 在中间. 因此根据这三种情况我们先看是否出现两个4连座即左 + 右. 如果没有则看是否有1个4连座即左或者右或者中. 为了判断座位占用情况, 我们使用三个bit mask来和记录当前行座位占用情况的integer进行&操作. 进行and操作如果结果不为0, 那么说明当前判断的4连座中至少有一个位置被占用了.

时间复杂度: O(n)
空间复杂度: O(n)