LeetCode 1386. 安排电影院座位
目录
题目描述
题意分析
电影院有
n排座位，每排 10 个，编号 1 到 10。reservedSeats给出已被预订的座位（行号 + 座位号）。一个「四人家庭」需要同一排中连续的四个座位，但不能跨过中间过道——过道位于 5 号和 6 号座位之间。问最多能安排多少个四人家庭。「不能跨过过道」这一句把可选位置从「任意连续四座」压缩到了极少数几种。逐一列举：
[1,4]需要占用 1 号座，[2,5]、[3,6]跨过道、[4,7]跨过道⋯⋯这里要小心，题目所说的「跨过道」指的是这四个座位横跨 5 和 6 的分界。真正合法的连续四座只有三种：左块[2,3,4,5]、中块[4,5,6,7]、右块[6,7,8,9]。中块
[4,5,6,7]看似跨越了 5 和 6，但题目的官方示意图明确把它算作合法——过道被理解为「不能把一个家庭从中间劈开」的物理限制，而 4 到 7 这一段被视为可以横跨。这是本题必须从示例反推出来的规则，纯看文字容易漏掉中块。由此得出一排最多能坐几个家庭：左块和右块互不重叠，可以同时使用，所以一排最多 2 个家庭；中块与左块共用 4、5 号座，与右块共用 6、7 号座，所以中块只能在左右两块都用不了的时候当作补救的第 1 个家庭。
1 号座和 10 号座不参与任何合法方案，所以预订这两个位置的记录可以直接丢弃，这是本题一个重要的化简。
约束里
n最大 $10^9$、reservedSeats长度最多 $10^4$。行数远大于预订数，说明绝大多数行是完全空的，不可能逐行遍历，只能对「有预订的行」做处理，其余行用乘法一次算完。这组约束是解法形态的决定性提示。边界要留意四点：同一行可能出现多条预订记录；预订记录可能全部落在 1 号或 10 号座，此时那一行其实和空行等价；答案上界是
2n，n取 $10^9$ 时结果达到 $2 \times 10^9$，仍在 32 位有符号整数范围内（上限约 $2.147 \times 10^9$）但已相当接近；有预订的行数最多 $10^4$，远小于n。
解法：位掩码统计座位
核心思路
n很大而预订记录很少，不能逐排扫描。只记录真正影响家庭座位块的排；其他排完全等价，每排直接贡献 2 个家庭。用
rowMask[row]表示一排的占用状态，第seat-1位为 1 表示该座位已预订。1 号和 10 号座位不属于任何候选块，可以忽略。三个候选掩码是：
- 左块
[2,5]：0b0000011110- 中块
[4,7]：0b0001111000- 右块
[6,9]：0b0111100000
(mask & block) == 0表示该块全部空闲。每排先独立检查互不重叠的左、右块；若二者都不可用，再检查中块。这个判断覆盖了每排的最优解：一排至多安排两个家庭，而唯一不重叠的两块组合是左块加右块；若两者都可用，答案就是 2。否则任何方案至多为 1，此时三个候选块中只要有一个可用就能达到 1。代码已检查左、右；只有它们都失败时，才需要用中块补上这一种可能。
总体不变量是：初始答案已包含所有未受影响排的最优贡献；遍历哈希表后，再逐排加入每个受影响排的最优贡献。因此最终和就是全局最优值。
解题步骤
- 遍历
reservedSeats，忽略座位 1 和 10；其余座位通过按位或写入对应排的掩码。- 设受影响排数为
rows.size()，先令答案为2 * (n - rows.size())。- 对每个掩码分别判断左块与右块，可用就各加 1。
- 若左右都不可用且中块可用，再加 1。
官方样例中，第 3 排只预订了 1、10 号座，因此仍按空排贡献 2；第 1 排只有中块可用，贡献 1；第 2 排只有左块可用，贡献 1，总计 4。
边界反例
n = 1, reservedSeats = [[1,3],[1,8]]中左右块都被阻塞，但中块[4,7]完整，答案为 1。若只检查左右块就会错误返回 0。
代码实现
import java.util.HashMap;
import java.util.Map;
class Solution {
public int maxNumberOfFamilies(int n, int[][] reservedSeats) {
int leftMask = 0b0000011110;
int midMask = 0b0001111000;
int rightMask = 0b0111100000;
Map<Integer, Integer> rowMask = new HashMap<>();
for (int[] r : reservedSeats) {
int row = r[0];
int seat = r[1];
if (seat >= 2 && seat <= 9) {
rowMask.put(row, rowMask.getOrDefault(row, 0) | (1 << (seat - 1)));
}
}
int res = (n - rowMask.size()) * 2;
for (int mask : rowMask.values()) {
boolean left = (mask & leftMask) == 0;
boolean right = (mask & rightMask) == 0;
if (left) {
res++;
}
if (right) {
res++;
}
if (!left && !right && (mask & midMask) == 0) {
res++;
}
}
return res;
}
}
func maxNumberOfFamilies(n int, reservedSeats [][]int) int {
leftMask := 0b0000011110
midMask := 0b0001111000
rightMask := 0b0111100000
rowMask := make(map[int]int)
for _, r := range reservedSeats {
row := r[0]
seat := r[1]
if seat >= 2 && seat <= 9 {
rowMask[row] |= 1 << (seat - 1)
}
}
res := (n - len(rowMask)) * 2
for _, mask := range rowMask {
left := (mask & leftMask) == 0
right := (mask & rightMask) == 0
if left {
res++
}
if right {
res++
}
if !left && !right && (mask&midMask) == 0 {
res++
}
}
return res
}
复杂度分析
- 时间复杂度：期望 $O(m)$，其中 $m$ 是预订记录数；建立哈希表和遍历受影响排都至多处理 $m$ 项。
- 空间复杂度：$O(r)$，其中 $r$ 是包含 2 到 9 号预订座位的排数，且 $r\le m$。
关键点总结
- 稀疏输入下只存异常排，其余排用“默认贡献乘数量”一次计算。
- 座位
seat映射到第seat-1位，块是否空闲可用一次按位与判断。- 左右块互不重叠；中块与两者都重叠，只能在左右都未选时补位。
- 1、10 号座位不影响任何候选块，过滤后
rowMask.size()才等于受影响排数。- 答案上界为 $2n$，在题目范围内仍可使用
int。
易错点总结
- 位号写成
1 << seat而块掩码仍按seat-1编码，会使所有占用错移一位。- 把中块与左右块同时计数。反例
[[1,8]]中左块和中块都空，但二者重叠，只能安排一个家庭。- 忽略中块。反例
[[1,3],[1,8]]中只有中块可用，正确答案为 1。- 用预订记录数代替受影响排数；同一排可有多条记录，必须按行聚合。
- 把 1、10 号座位所在排算作受影响排，会少算本可安排的两个家庭。
- 同一排的座位状态必须按位或累积，直接赋值会丢失之前的预订信息。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 191. 位1的个数 | 简单 | 位运算基本功，n & (n-1) 消最低位 1 的技巧 |
| 338. 比特位计数 | 简单 | 用递推复用已算结果，训练把位运算与 DP 结合 |
| 78. 子集 | 中等 | 用 n 位掩码枚举所有子集，是「小状态用整数表示」的最典型场景 |
| 187. 重复的DNA序列 | 中等 | 把定长字符串压成整数做哈希，同为「小规模状态编码成整数」 |
| 1178. 猜字谜 | 困难 | 用 26 位掩码表示字母集合，还要枚举子集做匹配 |
| 982. 按位与为零的三元组 | 困难 | 大量按位与查询，需要预处理成计数数组来避免三重循环 |
| 201. 数字范围按位与 | 中等 | 从位的角度推导公共前缀，与本题一样靠位性质而非枚举 |
| 698. 划分为k个相等的子集 | 中等 | 用位掩码记录已选元素做状态压缩搜索，掩码规模由元素个数决定 |
| 847. 访问所有节点的最短路径 | 困难 | 状态是「当前点 + 已访问集合掩码」，掩码作为 BFS 状态的一维 |
| 452. 用最少数量的箭引爆气球 | 中等 | 同为「有限位置放置」的贪心，靠排序后按右端点决策 |
| 435. 无重叠区间 | 中等 | 选取互不重叠的最多区间，与本题「左右块不重叠可同选」的判断同源 |
| 253. 会议室 II | 中等 | 资源分配类问题，重点是识别重叠并计数峰值 |
| 763. 划分字母区间 | 中等 | 先预处理出每个字母的最远位置，再一趟贪心切分，同属「预处理 + 单趟决策」 |
| 56. 合并区间 | 中等 | 区间重叠关系的基础题，帮助理清「相交就不能同时选」的判定 |