LeetCode 1386. 安排电影院座位

约 5 分钟
文章信息 6 个分类 4 个标签
分类
LeetCode CodeTop 中等 未解决 1-2 华为
标签
数组 哈希表 贪心 位运算

题目描述

✅ 1386. 安排电影院座位

image-20260929082529366

image-20260929082529494

image-20260929082529605

题意分析

电影院每排十个座位，四人小组必须坐在同一排，并只能使用 2—5、4—7、6—9 这三个允许的座位块。一个块里只要有预订座位就不能使用，每个座位最多分配给一组。

求所有排合计最多可以安排多少组。不同排之间互不影响，排数可达 10^9，但预订记录最多 10^4 条，因此不能逐排建立座位数组或逐排扫描。

解法：位掩码统计座位

核心思路

[!blue]

一排最多安排两组，只有左块 2—5 与右块 6—9 可以同时使用；中块 4—7 与它们都有重叠。所以每排最优安排可以直接分类：左右块都空闲就放两组，只空闲一个就放一组，两边都不可用时再尝试中块，仍不可用则放零组。

这个选择不会漏掉更好安排。只要选中中块，本排就最多一组，不可能再叠加左右块；因此任一侧块可用时，选择它已经不比选择中块差。只有左右都被挡住时，中块才可能补回一组。

用一个整数的不同二进制位表示一排座位是否已预订，座位 seat 对应第 seat - 1 位。将三个候选块也写成掩码，mask & blockMask == 0 就表示该块没有任何被占座位。同一排的多条记录通过按位或累积，不能相互覆盖。

座位一和十不属于任何候选块，因此这两个位置的预订可以忽略。哈希表只记录二到九号座位受影响的排；其他排无论是否预订了一号或十号座位，都仍能安排左右两组。

先用“总排数减受影响排数”乘二计入默认贡献，再逐个处理哈希表里的受影响排。这样工作量只与预订记录有关，各排答案独立相加就是全局最大值。

解题步骤

  1. 准备左右和中间三个候选块的掩码。
  2. 扫描预订记录，只把二到九号座位按位或到对应排的占用掩码。
  3. 对未记录的排，每排先计入两组。
  4. 对受影响排，分别检查左块和右块，空闲就各加一组。
  5. 仅当左右都不可用时检查中块，若空闲再补一组，最后返回总数。

代码实现

class Solution {
    public int maxNumberOfFamilies(int n, int[][] reservedSeats) {
        // 位号为座位号减一，三个掩码对应题目允许的三个座位块。
        int leftMask = 0b0000011110;
        int midMask = 0b0001111000;
        int rightMask = 0b0111100000;

        Map<Integer, Integer> rowMask = new HashMap<>();

        for (int[] r : reservedSeats) {
            int row = r[0];
            int seat = r[1];

            // 两端座位不影响任何候选块，可以不记录。
            if (seat >= 2 && seat <= 9) {
                rowMask.put(row, rowMask.getOrDefault(row, 0) | (1 << (seat - 1)));
            }
        }

        // 未受影响的排统一贡献两组，不逐排遍历。
        int res = (n - rowMask.size()) * 2;

        for (int mask : rowMask.values()) {
            boolean left = (mask & leftMask) == 0;
            boolean right = (mask & rightMask) == 0;

            if (left) {
                res++;
            }

            if (right) {
                res++;
            }

            // 中块与左右块都重叠，只能在左右都不可用时补一组。
            if (!left && !right && (mask & midMask) == 0) {
                res++;
            }
        }

        return res;
    }
}

func maxNumberOfFamilies(n int, reservedSeats [][]int) int {
    // 位号为座位号减一，三个掩码对应题目允许的三个座位块。
    leftMask := 0b0000011110
    midMask := 0b0001111000
    rightMask := 0b0111100000

    rowMask := make(map[int]int)
    for _, r := range reservedSeats {
        row := r[0]
        seat := r[1]
        // 两端座位不影响任何候选块，可以不记录。
        if seat >= 2 && seat <= 9 {
            rowMask[row] |= 1 << (seat - 1)
        }
    }

    // 未受影响的排统一贡献两组，不逐排遍历。
    res := (n - len(rowMask)) * 2
    for _, mask := range rowMask {
        left := (mask & leftMask) == 0
        right := (mask & rightMask) == 0
        if left {
            res++
        }
        if right {
            res++
        }
        // 中块与左右块都重叠，只能在左右都不可用时补一组。
        if !left && !right && (mask&midMask) == 0 {
            res++
        }
    }
    return res
}

复杂度分析

设预订记录数为 $m$，其中影响候选座位块的不同排数为 $r$。

  • 时间复杂度：期望 $O(m)$，构建哈希表后每个受影响排只检查三个固定掩码，且 $r\le m$。
  • 辅助空间复杂度：$O(r+1)$，保存受影响排的占用状态，不随总排数线性增长。

关键点总结

[!green]

  • 左右块能同时安排，中块只提供一种替代的一组方案。
  • 位掩码同时记录一排全部预订，按位与判断候选块是否空闲。
  • 未受影响的排统一计两组，只遍历少量受影响排。

易错点总结

[!yellow]

  • 忽略中块会漏掉两侧受阻而中间空闲的一组方案。
  • 把中块与左块或右块同时计数，会重复使用共享座位。
  • 默认贡献要减去不同的受影响排数，不能减去预订记录条数。
  • 更新占用掩码必须使用按位或，直接赋值会丢失同排之前的预订。
  • 座位号与位号相差一，预订位移和块掩码必须保持同一编号规则。

相似题目

题目 难度 关联与区别
1349. 参加考试的最大学生数 困难 同样可用位掩码表示一行座位，原题还限制前后排，本题各行独立且只检查少数合法四人块。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2024/16762708
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！