Leetcode每日一题 —— 1386. 安排电影院座位

力扣 LeetCode

1386. 安排电影院座位 - 力扣（LeetCode）

1386. 安排电影院座位 - [https://assets.leetcode.cn/aliyun-lc-upload/uploads/2020/03/21/cinema_seats_1.png]

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

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

思路

首先看输入规模，发现最多可能有 n=10^9 行！（你这电影院真大啊！）我们难以直接标注每个位置的状态。

注意到预留的座位最多只有 10000 个，因此在 n 较大时显得较为稀疏，不一定所有行都有预留的座位:

- 对于没有任何预留座位的行，可以安排 2 个组；

- 对于有预留座位的行，可能安排 2, 1, 0 个组。

因此我们其实只需要扫描处理第 2 种情况（找到所有被占用的行，显然可以用哈希表）。注意到每个位置只有占用 / 未占用两个状态，对应 1 / 0，可以直接用 10 个二进制位来表示每行的状态，检查安排情况只需要进行位运算即可。

另外注意题目要求，安排时只能坐在特定几组的位置上，并不是找到 4 个连续空位就可以的。

代码```
class Solution {
public:
int maxNumberOfFamilies(int n, vector<vector<int>>& reservedSeats) {
// 注意行数，最多可能有 10^9 行！
// 被预留的座位最多 10000 个，n 很大时显得较稀疏
// 值得注意的是如果一行没有任何预留，那么最多只能安排两组
// 有预留则可能是 2, 1, 0 组

// 可以用哈希表来存每行的状态，每个位置只有占用 / 未占用两个状态，因此可以用 10 个二进制位来表达
// 被占用的行以及对应的二进制位
unordered_map<int,int> states;
int occupied=0; // 统计被占用的行数
for(auto& r:reservedSeats){
if(states.count(r[0])==0){
occupied++;
states[r[0]]=0;
}
states[r[0]]|=(1<<(10-r[1]));
}
int res=0;
// 注意只能安排到指定位置
int left=0b0111100000;
int right=0b0000011110;
int mid=0b0001111000;
// 枚举每个被占用的行，检查各自能分配多少座位
for(auto it=states.begin();it!=states.end();it++){
int s=it->second;
if((s&left)==0&&(s&right)==0){
// 两侧座位未被占用
res+=2;
}else if((s&left)==0||(s&right)==0||(s&mid)==0){
// 有一段没有被占用
res++;
}
}
// 其余没有被占用的行每行两个
res+=(n-occupied)*2;
return res;
}
};