安排电影院座位

标签: 贪心 位运算 数组 哈希表

难度: Medium

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

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

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

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

Submission

运行时间: 66 ms

内存: 19.6 MB

class Solution:
    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:
        tab = defaultdict(int)
        for r, c in reservedSeats:
            if c < 2 or c > 9:
                continue
            tab[r] += 1<<(c-2)
        ret = (n - len(tab)) * 2
        l = 0b00001111
        r = 0b11110000
        m = 0b11000011
        for row in tab:
            if tab[row]|r == r:
                ret += 1
            elif tab[row]|l == l:
                ret += 1
            elif tab[row]|m == m:
                ret += 1
        return ret

Explain

此题解使用了位操作和哈希表来有效地计算最多可以安排的4人家庭数量。首先，使用哈希表（'tab')记录那些有至少一个被预订的座位的行，键是行号，值是一个整数，对应于行中被预订的座位的位标记。仅关注第2到第9列的座位，因为第1列和第10列的座位无法容纳一个完整的4人家庭。使用位操作将座位映射到一个8位的整数中。然后，对于那些没有任何预订记录的行，因为每行可以容纳两个4人家庭，所以简单地将这些行的家庭数量乘以2加到结果中。对于有预订记录的行，检查通过位掩码判断是否可以安排家庭。如果能在左侧（2-5座）、右侧（6-9座）或中间（4-7座）安排，则相应地增加计数。如果一行能同时在左侧和右侧安排家庭，则可以安排两个家庭，否则检查是否可以在中间安排一个家庭。

时间复杂度: O(m)

空间复杂度: O(m)

class Solution:
    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:
        tab = defaultdict(int)
        # 记录每行被预订的座位的位表示
        for r, c in reservedSeats:
            if c < 2 or c > 9:
                continue
            tab[r] += 1<<(c-2)
        # 计算完全没有被预订的行可以安排的家庭数量
        ret = (n - len(tab)) * 2
        # 定义左中右的位掩码
        l = 0b00001111
        r = 0b11110000
        m = 0b11000011
        # 检查每行能安排的家庭数量
        for row in tab:
            if tab[row]|r == r:
                ret += 1
            elif tab[row]|l == l:
                ret += 1
            elif tab[row]|m == m:
                ret += 1
        return ret

Explore

因为一个4人家庭需要连续4个座位，所以第1列和第10列的座位实际上无法独立容纳一个完整的4人家庭。只有第2列到第9列的座位才能可能组成两个独立的4人家庭区域（例如2-5列和6-9列），因此只需要关注这些座位。使用8位整数可以精确地表示这些座位的占用情况，使得位操作可以高效地应用于检查和计算可用的家庭座位区域。

`l`代表左侧的座位区域，涵盖2-5列，对应位掩码是`0b00001111`。`r`代表右侧的座位区域，涵盖6-9列，对应位掩码是`0b11110000`。`m`代表中间的座位区域，涵盖4-7列，对应位掩码是`0b11000011`。这些位掩码是根据家庭座位需要连续4个空位来定义的，确保各个区域可以容纳一个4人家庭，而具体的位值则是直接反映了每个区域座位的位置。

如果一行没有任何座位被预订，那么第2列到第9列的所有座位都是空的。这允许在2-5列和6-9列各自安排一个4人家庭，共两个家庭。这种情况下，每行的空座位充足，没有任何障碍阻止两个家庭的安排。因此，在没有预订的情况下，可以最大化利用座位，每行安排两个家庭。

对于已有部分座位被预订的行，算法首先将这些座位的占用情况表示为一个8位的整数。然后使用位掩码`l`, `r`, `m`来检查是否能在左侧、右侧或中间安排一个家庭。使用位或操作（`|`）和比较操作来确定是否所有需要的座位都是空的。例如，如果`(tab[row] | l) == l`成立，说明左侧4个座位（2-5列）都是空的，可以安排一个家庭。同理，检查右侧和中间区域。如果一行中左侧和右侧都可以安排家庭，则总计可以安排两个家庭，否则检查中间区域是否可以安排一个家庭。