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

思路

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

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

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


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;

    }

};