What is the best way to handle large n with few reservedSeats?

Use a hash table to store only rows with reservations, skipping empty rows and computing counts directly to maintain efficiency.

Can a four-person group sit across an aisle?

Only in the middle split case (seats 4-7), where two seats can sit on each side; otherwise, aisles break adjacency.

Why use bit manipulation in this problem?

Bit masks allow fast checks of multiple contiguous seats per row to determine if a group can be seated without iterating each seat.

How many groups can one row hold?

At most two groups per row, unless reserved seats prevent one or both possible four-seat blocks.

Does this problem follow the array scanning plus hash lookup pattern?

Yes, the core approach scans potential blocks per row and uses a hash table for reserved seat lookups to avoid unnecessary iteration.

#1386

Medium

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

安排电影院座位

如上图所示，电影院的观影厅中有 n 行座位，行编号从 1 到 n ，且每一行内总共有 10 个座位，列编号从 1 到 10 。给你数组 reservedSeats ，包含所有已经被预约了的座位。比如说， reservedSeats[i]=[3,8] ，它表示第 3 行第 8 个座位被预约了。请你…

数组哈希表贪心位运算

题目描述

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

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

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

示例 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

示例 3：

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

提示：

1 <= n <= 10^9
1 <= reservedSeats.length <= min(10*n, 10^4)
reservedSeats[i].length == 2
1 <= reservedSeats[i][0] <= n
1 <= reservedSeats[i][1] <= 10
所有 reservedSeats[i] 都是互不相同的。

lightbulb

解题思路

方法一：哈希表 + 状态压缩

我们用哈希表 $d$ 来存储所有已经被预约的座位，其中键为行号，值为该行上已经被预约的座位的状态，即一个二进制数，第 $j$ 位为 $1$ 表示第 $j$ 个座位已经被预约，为 $0$ 表示第 $j$ 个座位尚未被预约。

我们遍历 $reservedSeats$ ，对于每个座位 $(i, j)$ ，将第 $j$ 个座位（对应低位的第 $10-j$ 位）的状态加入到 $d[i]$ 中即可。

对于没有出现在哈希表 $d$ 中的行，我们可以任意安排 $2$ 个家庭，因此，初始答案为 $(n - len(d)) \times 2$ 。

接下来，我们遍历哈希表中每一行的状态，对于每一行，我们依次尝试安排 $1234, 5678, 3456$ 这几种情况，如果某种情况可以安排，我们就将答案加 $1$ 。

遍历结束后，我们就得到了最终的答案。

时间复杂度 $O(m)$ ，空间复杂度 $O(m)$ ，其中 $m$ 是 $reservedSeats$ 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

class Solution:
    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:
        d = defaultdict(int)
        for i, j in reservedSeats:
            d[i] |= 1 << (10 - j)
        masks = (0b0111100000, 0b0000011110, 0b0001111000)
        ans = (n - len(d)) * 2
        for x in d.values():
            for mask in masks:
                if (x & mask) == 0:
                    x |= mask
                    ans += 1
        return ans

speed

复杂度分析

指标	值
时间	complexity is O(R) where R is the number of rows with reserved seats, since each reserved row is scanned with constant checks; empty rows are computed directly. Space complexity is O(R) to store reserved seat positions in a hash table.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Check if your solution handles rows with no reserved seats efficiently.
question_mark
They may ask why a row cannot always hold two groups if seats are partially reserved.
question_mark
Expect follow-up on using bit manipulation versus simple greedy checks for blocks.

warning

常见陷阱

外企场景

error
Ignoring the middle block split across an aisle and incorrectly counting four-person groups.
error
Assuming all rows with reserved seats can only fit one group without scanning possible blocks.
error
Iterating over n rows directly instead of leveraging hash lookup for sparse reservations.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Change the group size from four to k and adjust block checks accordingly.
arrow_right_alt
Introduce variable row lengths to test adaptive array scanning strategies.
arrow_right_alt
Limit reservedSeats length to small numbers but n extremely large to test hash lookup efficiency.

help

常见问题

外企场景

继续练习

#1338 数组大小减半 #1442 形成两个异或相等数组的三元组数目 #1296 划分数组为连续数字的集合