---

1386. 安排电影院座位

• 标签：贪心、位运算、数组、哈希表
• 难度：中等

题目链接

• 1386. 安排电影院座位 - 力扣

题目大意

描述：电影院有 $n$ 排座位，每排 $10$ 个座位，编号 $1$ 到 $10$。一些座位已被预约。一个家庭共 $4$ 人，需要安排在同一排的连续 $4$ 个座位上。可选的连续 $4$ 座区间为 $[2,5]$、$[4,7]$、$[6,9]$。

要求：返回最多能安排多少个这样的 $4$ 人家庭。

说明：

• $1 \le n \le 10^9$。
• $1 \le reservedSeats.length \le 10^4$。

示例：

• 示例 1：

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

• 示例 2：

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

解题思路

思路 1：位运算 + 哈希表

1. 核心思想

每排 $10$ 个座位，只有中间 $8$ 个（$2$-$9$）在考虑的 $3$ 个连续区间中。用 $8$ 位二进制数表示中间 $8$ 个座位的占用状态。

对每排，用位掩码标记已预约座位（座位 $2$ 对应最低位）。检查三个区间 $[2,5]$、$[4,7]$、$[6,9]$ 是否为空，贪心地安排尽可能多的家庭。

未受预约影响的行可以安排 $2$ 个家庭（$[2,5]$ + $[6,9]$）。

2. 具体步骤

第 1 步：用哈希表 $row\_mask$ 记录每排的座位占用情况（只记录有预约的行）。

第 2 步：对每行，检查三个区间：

• $[2,5]$：掩码 0b11110000（座位 $2$-$5$）
• $[4,7]$：掩码 0b00111100（座位 $4$-$7$）
• $[6,9]$：掩码 0b00001111（座位 $6$-$9$）

优先安排两个不相邻的区间（$[2,5]$ + $[6,9]$），其次安排中间的 $[4,7]$。

第 3 步：未受影响的排每排 $2$ 个家庭。

思路 1：代码

class Solution:
    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:
        row_mask = {}
        for r, c in reservedSeats:
            if c in (1, 10):
                continue
            row_mask[r] = row_mask.get(r, 0) | (1 << (c - 2))

        left = 0b11110000    # 座位 2,3,4,5
        mid = 0b00111100     # 座位 4,5,6,7
        right = 0b00001111   # 座位 6,7,8,9

        ans = (n - len(row_mask)) * 2  # 没有预约的行可以安排 2 个

        for mask in row_mask.values():
            if mask & left == 0 and mask & right == 0:
                ans += 2
            elif mask & left == 0 or mask & mid == 0 or mask & right == 0:
                ans += 1

        return ans

思路 1：复杂度分析

• 时间复杂度：$O(k)$，$k$ 是预约座位数。
• 空间复杂度：$O(k)$。