1386.安排电影院座位：哈希表+位运算

【LetMeFly】1386.安排电影院座位：哈希表+位运算

力扣题目链接：https://leetcode.cn/problems/cinema-seat-allocation/

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

给定一个二维数组 reservedSeats ，其中 reservedSeats[i] = [rowi, seati] 表示第 rowi 行的座位 seati 已经被预定。

四人小组必须被安排在同一排的四个座位上。该小组可以坐在以下座位块之一：

• 座位 2, 3, 4, 5
• 座位 4, 5, 6, 7
• 座位 6, 7, 8, 9

只有当该块中的所有座位都 没有 被预订时，才能使用该块。每个座位 最多 只能分配给一个小组。

返回一个整数，表示可以分配的 最大 四人小组数量。

 

示例 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 <= 109
• 1 <= reservedSeats.length <= min(10 * n, 104)
• reservedSeats[i] == [rowi, seati]
• 1 <= rowi <= n
• 1 <= seati <= 10
• 所有 reservedSeats[i] 都是互不相同的。

What a huge cinema.

解题方法：哈希表 + 位运算

$n$的范围是$10^9$所以需要使用哈希表离散化处理，可以使用一个哈希表记录每一行的预订情况：

怎么记录某行的预订情况呢？使用一个整数即可。某行第$i$个座位被预订的话，就将第$i$位置1。

遍历一遍reservedSeats得到哈希表，看下哈希表大小（即有多少行被预订）。

• 对于没有被预订的行，最多可以安排两个四人小组。
• 对于有预订的行：如果$2\sim 9$都空则可座两组；否则如果$2\sim 5$空或者$4\sim 7$空或者$6\sim 9$空则可座一组。

怎么看某行$2\sim 9$是否全空呢？可以使用位运算，提前算出$2\sim 9$位都为1的mask，和此行预订情况做或运算，结果非零则全空。

时空复杂度

• 时间复杂度$O(len(reservedSeats))$
• 空间复杂度$O(len(reservedSeats))$

AC代码

C++

/*
 * @LastEditTime: 2026-08-19 11:43:10
 */
const int mask1 = 1 << 2 | 1 << 3 | 1 << 4 | 1 << 5;
const int mask2 = 1 << 4 | 1 << 5 | 1 << 6 | 1 << 7;
const int mask3 = 1 << 6 | 1 << 7 | 1 << 8 | 1 << 9;
const int mask4 = mask1 | mask3;

class Solution {
public:
    int maxNumberOfFamilies(int n, vector<vector<int>>& reservedSeats) {
        unordered_map<int, int> reserved;
        for (vector<int>& people : reservedSeats) {
            reserved[people[0]] |= 1 << people[1];
        }
        int ans = (n - reserved.size()) * 2;
        for (auto [_, line] : reserved) {
            if (!(line & mask4)) {
                ans += 2;
            } else if (!(line & mask1) || !(line & mask2) || !(line & mask3)) {
                ans += 1;
            }
        }
        return ans;
    }
};

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

千篇源码题解已开源