秋招每日一题T32——安排电影院座位

题目描述

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

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

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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/cinema-seat-allocation
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

〇整体解题方向为：哈希表 ＋ 位运算。
①首先可以开一个unordered_map，用于存储每一行被占用座位的位图。一行总共有十个座位，如果某个座位已经被占，那么该位为1，否则为0。
②根据题目描述，如果一行有座位满足条件，那么最好的情况可以是安排两个四人座位（整行都没有人，或者只在两个角），次优的情况是只能安排一个座位（中间四人）。
③对哈希表进行遍历（即，每一行），由于哈希表的键值是位图，因此使用0x1e、0x1e0、0x78与键值进行与运算，分情况判断。（前面的三个16进制数，对应的是座位上是否有人）

代码

class Solution {
public:
    int maxNumberOfFamilies(int n, vector<vector<int>>& reservedSeats) {
        unordered_map<int, int> mp;
        for(auto &v:reservedSeats){
            mp[v[0]] |= 1 << (v[1]-1);
        }
        int ans = (n-mp.size())*2;
        for(auto &r: mp){
            if(!(r.second & 0x1e) && !(r.second & 0x1e0)){
                ans += 2;
            }
            else if(!(r.second & 0x1e) || !(r.second & 0x1e0) || !(r.second & 0x78)){
                ans ++;
            }
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19