原题链接:
https://leetcode.cn/problems/cinema-seat-allocation/
这题首先要注意到的一个信息是 1 <= n <= 10^9 即n 范围为10^9 也就是说 即使O(n) 也不行
但是有注意到 1 <= reservedSeats.length <= min(10*n, 10^4) 即要占座位的数量只有10^4 是一个比较小的数 因此可以考虑逆向求解 求出最大正确答案数 2 * n(关于正确答案也比较简单 因为根据题意最多每行只能放两个家庭 )
然后就是可以进行二进制优化 用一个二进制数代表每行的座位排列 1 表示该位已经被占 0 表示空位 将占座信息记录到hash表中 然后反向排除即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:
        d = defaultdict(int)
        for x,y in reservedSeats:
            if y == 1 or y == 10:
                continue
            # 将2-9 映射到0-8 方便后续判断 所以要左移y-2
            d[x] |= 1 << y-2

        ans = 2 *  n - 2 * len(d)
        left = 0b11110000
        mid = 0b00111100
        right = 0b00001111
        for v in d.values():
            if not (v & left) or not (v&mid) or not (v&right):
                ans = ans + 1
        return ans