LeetCode 1386. 安排电影院座位

Categories:

题目描述
思路分析
1. 解法一：位掩码统计座位（推荐）
相似题目

题目描述

✅ 1386. 安排电影院座位

思路分析

解法一：位掩码统计座位（推荐）

核心思路：

用位掩码表示每一排的占座情况，仅需关注 2~9 号座位。

左块 [2..5]、中块 [4..7]、右块 [6..9] 判断是否可放置。

无预定座位的行可放置 2 个家庭。

复杂度分析：

时间复杂度：O(m)，其中 m 为预定座位数。

空间复杂度：O(m)。

import java.util.HashMap;
import java.util.Map;

class Solution {
    public int maxNumberOfFamilies(int n, int[][] reservedSeats) {
        int leftMask = 0b0000111100;
        int midMask = 0b0011110000;
        int rightMask = 0b1111000000;

        Map<Integer, Integer> rowMask = new HashMap<>();
        for (int[] r : reservedSeats) {
            int row = r[0];
            int seat = r[1];
            if (seat >= 2 && seat <= 9) {
                int mask = rowMask.getOrDefault(row, 0);
                mask |= 1 << (seat - 1);
                rowMask.put(row, mask);
            }
        }

        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 := 0b0000111100
    midMask := 0b0011110000
    rightMask := 0b1111000000

    rowMask := make(map[int]int)
    for _, r := range reservedSeats {
        row := r[0]
        seat := r[1]
        if seat >= 2 && seat <= 9 {
            mask := rowMask[row]
            mask |= 1 << (seat - 1)
            rowMask[row] = mask
        }
    }

    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
}

相似题目

题目	难度	考察点
849. 到最近的人的最大距离	中等	计数
855. 考场就座	中等	贪心
1229. 安排会议日程	中等	区间
452. 用最少数量的箭引爆气球	中等	贪心
57. 插入区间	中等	区间

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2024/16762708