LeetCode-1386 安排电影院座位

题目描述

如上图所示，电影院的观影厅中有 $n$ 行座位，行编号从 $1$到 $n$ ，且每一行内总共有 $10$ 个座位，列编号从 $1$ 到 $10$ 。

给你数组 reservedSeats ，包含所有已经被预约了的座位。比如说，researvedSeats[i]=[3,8] ，它表示第 $3$ 行第 $8$ 个座位被预约了。

请你返回 最多能安排多少个 $4$ 人家庭 。$4$ 人家庭要占据 同一行内连续 的 $4$ 个座位。隔着过道的座位（比方说 $[3,3]$ 和 $[3,4]$）不是连续的座位，但是如果你可以将 $4$ 人家庭拆成过道两边各坐 $2$ 人，这样子是允许的。

示例 1：

1
2
3
输入：n = 3, reservedSeats = [[1,2],[1,3],[1,8],[2,6],[3,1],[3,10]]
输出：4
解释：上图所示是最优的安排方案，总共可以安排 4 个家庭。蓝色的叉表示被预约的座位，橙色的连续座位表示一个 4 人家庭。

示例 2：

1
2
输入：n = 2, reservedSeats = [[2,1],[1,8],[2,6]]
输出：2

示例 3：

1
2
输入：n = 4, reservedSeats = [[4,3],[1,4],[4,6],[1,7]]
输出：4

位运算 - $O(N)$

二进制表示

我们观察发现所有满足条件的家庭座位如下：

  • 红色方框 分别表示三种符合条件的家庭座位
  • 两侧两个座位紫色方框不会构成家庭座位

问题转换成：判断给定的座位每一行是否存在上述三种情况即可

如果我们用 $0/1$ 分别对每个座位是否预定进行标记，那么每一排座位可以看成一个二进制串：

  • $0$ 表示 没有 被预定
  • $1$ 表示被预定了

由于两侧位置不会构成家庭座位，因此直接忽略即可

位运算

此时，我们对 上述三种符合条件的家庭座位 分别用二进制串进行表述：

我们得到了三种符合条件的家庭座位对应的二进制串：

  • $00001111$
  • $11110000$
  • $11000011$

那么：如果我们也将 问题给定的每一行座位利用同样的方式进行标记得到一个二进制串 $v$，那么每一行座位是否存在上述三种符合条件情况等价于：

  • 符合 $00001111$ 这种情况等价于：$v$ 的前 $4$ 位是否均是 $0$
  • 符合 $11110000$ 这种情况等价于：$v$ 的后 $4$ 位是否均是 $0$
  • 符合 $11000011$ 这种情况等价于：$v$ 的中间 $4$ 位是否均是 $0$

获取一个二进制某些位置的数值我们可以利用 与 运算:

算法流程

  • 依次计算问题给定座位的每一行座位的家庭座位数量，最后累加
  • 两侧两个位置由于均不会构成家庭座位，因此忽略掉
  • 当前行利用二进制进行表示为 $v$
    • 如果当前行不存在任何预定的位置，则当前行家庭数量为 $2$
    • 如果存在预定位置：可以知道三种符合条件最多符合其中 $1$ 种
      • 分别获取对应位置二进制串：11110000 & v, 11110000 & v, 001111 & v
      • 如果这三个值，存在一个 $0$，则说明符合三种状态的某个，当前行家庭数量为 $1$

时间复杂度 - $O(N)$

  • 由于要枚举 reservedSeats 数组，复杂度为 $O(N)$，其中 $N$ 为 reservedSeats 数组长度。

代码

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
func maxNumberOfFamilies(n int, reservedSeats [][]int) int {
    // 创建哈希表记录每个每一行座位的二进制表示
    S := make(map[int]int)
    // 依次处理每个预定的位置
    for _, v := range reservedSeats {
        // x: 对应行编号，y: 预定的位置
        x, y := v[0], v[1]
        // 两侧位置直接忽略，如果是中间位置的话，记录其二进制表示
        if y != 1 && y != 10 {
            // 将当前预定的位置用二进制表示
            S[x] |= 1 << (y - 2)
        }
    }
    // left, mid, right 分别用于判断是否满足三种符合条件的状态
    left, mid, right := 0b11110000, 0b00111100, 0b00001111
    // 剩余没有任何预定座位的行的家庭座位数量是 2
    res := (n - len(S)) * 2
    // 依次处理每个有预定座位的行
    for _, v := range S {
        // 具体见上面讲解部分
        // v & left/mid/right：分别获取前4位/中间4位/后4位
        // 如果获取到的是全 0 的话，那么说明是符合当前状态的，那么预定座位数量是 1
        if ((v & left) == 0) || ((v & mid) == 0) || ((v & right) == 0) { res++ }
    }
    return res
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    unordered_map<int, int> S;

    int maxNumberOfFamilies(int n, vector<vector<int>>& reservedSeats) {
        for (auto& v : reservedSeats) {
            int x = v[0], y = v[1];
            if (y != 1 && y != 10) S[x] |= 1 << y - 2;
        }
        int left = 0b11110000, mid = 0b00111100, right = 0b00001111;
        int res = (n - S.size()) * 2;
        for (auto& [_, v] : S) res += !(v & left) || !(v & mid) || !(v & right);
        return res;
    }
};