Medium

题目描述

一个影院有 n 排座位，编号从 1 到 n，每排有 10 个座位，编号从 1 到 10。

给你数组 reservedSeats，包含所有已经被预订的座位，例如 reservedSeats[i] = [3,8] 表示第 3 排第 8 号座位被预订了。

请你返回可以安排的四人家庭的最大数目，一个四人家庭占据同一排中四个相邻的座位。跨过过道的座位（比如 [3,3] 和 [3,4]）不被认为是相邻的，但是有一种特殊情况，如果一个四人家庭可以被过道分割成两部分，那么过道可以分割一个四人家庭的中间，也就是每边坐两个人。

示例 1：

输入：n = 3, reservedSeats = [[1,2],[1,3],[1,8],[2,6],[3,1],[3,10]]
输出：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] 都是互不相同的。

解题思路

解题思路

这道题的关键是理解座位布局和四人家庭的可能安排方式。每排有10个座位，分为三个区域：1-2（左侧），3-4-5-6-7-8（中间），9-10（右侧）。

可能的四人家庭安排方式：

  1. 座位 2-3-4-5（左区域）
  2. 座位 4-5-6-7（左中区域）
  3. 座位 6-7-8-9（右中区域）

贪心策略：

  • 对于没有预订座位的行，每行可以安排2个家庭（方式1+3或者方式2）
  • 对于有预订座位的行，需要检查哪些安排方式仍然可行
  • 优先选择不冲突的组合，最多每行2个家庭

算法步骤：

  1. 统计每行的预订座位情况
  2. 对于有预订的行，使用位操作或集合检查可行的安排
  3. 对于未出现在预订列表中的行，每行贡献2个家庭
  4. 求和得到最终结果

时间复杂度优化： 由于n可能很大（10^9），但预订座位最多10^4个，我们只需要处理有预订的行，其他行都按每行2个家庭计算。

代码实现

class Solution {
public:
    int maxNumberOfFamilies(int n, vector<vector<int>>& reservedSeats) {
        unordered_map<int, int> rowMask;
        
        // 构建每行的预订座位掩码
        for (auto& seat : reservedSeats) {
            int row = seat[0];
            int col = seat[1];
            if (col >= 2 && col <= 9) {  // 只关心2-9的座位
                rowMask[row] |= (1 << (col - 2));
            }
        }
        
        int result = 0;
        
        // 处理有预订座位的行
        for (auto& [row, mask] : rowMask) {
            int families = 0;
            // 检查左区域 (2,3,4,5) -> 位置 (0,1,2,3)
            if ((mask & 15) == 0) {  // 15 = 1111
                families++;
                mask |= 15;  // 标记这些位置已使用
            }
            // 检查右区域 (6,7,8,9) -> 位置 (4,5,6,7)
            if ((mask & 240) == 0) {  // 240 = 11110000
                families++;
            }
            // 如果左右都不能放，尝试中间区域 (4,5,6,7) -> 位置 (2,3,4,5)
            if (families == 0 && (mask & 60) == 0) {  // 60 = 111100
                families = 1;
            }
            result += families;
        }
        
        // 未出现在预订列表中的行，每行2个家庭
        result += (n - rowMask.size()) * 2;
        
        return result;
    }
};

class Solution:
    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:
        row_mask = {}
        
        # 构建每行的预订座位掩码
        for row, col in reservedSeats:
            if 2 <= col <= 9:  # 只关心2-9的座位
                if row not in row_mask:
                    row_mask[row] = 0
                row_mask[row] |= (1 << (col - 2))
        
        result = 0
        
        # 处理有预订座位的行
        for row, mask in row_mask.items():
            families = 0
            # 检查左区域 (2,3,4,5) -> 位置 (0,1,2,3)
            if (mask & 15) == 0:  # 15 = 1111
                families += 1
                mask |= 15  # 标记这些位置已使用
            # 检查右区域 (6,7,8,9) -> 位置 (4,5,6,7)
            if (mask & 240) == 0:  # 240 = 11110000
                families += 1
            # 如果左右都不能放，尝试中间区域 (4,5,6,7) -> 位置 (2,3,4,5)
            if families == 0 and (mask & 60) == 0:  # 60 = 111100
                families = 1
            result += families
        
        # 未出现在预订列表中的行，每行2个家庭
        result += (n - len(row_mask)) * 2
        
        return result

public class Solution {
    public int MaxNumberOfFamilies(int n, int[][] reservedSeats) {
        Dictionary<int, int> rowMask = new Dictionary<int, int>();
        
        // 构建每行的预订座位掩码
        foreach (var seat in reservedSeats) {
            int row = seat[0];
            int col = seat[1];
            if (col >= 2 && col <= 9) {  // 只关心2-9的座位
                if (!rowMask.ContainsKey(row)) {
                    rowMask[row] = 0;
                }
                rowMask[row] |= (1 << (col - 2));
            }
        }
        
        int result = 0;
        
        // 处理有预订座位的行
        foreach (var kvp in rowMask) {
            int mask = kvp.Value;
            int families = 0;
            
            // 检查左区域 (2,3,4,5) -> 位置 (0,1,2,3)
            if ((mask & 15) == 0) {  // 15 = 1111
                families++;
                mask |= 15;  // 标记这些位置已使用
            }
            // 检查右区域 (6,7,8,9) -> 位置 (4,5,6,7)
            if ((mask & 240) == 0) {  // 240 = 11110000
                families++;
            }
            // 如果左右都不能放，尝试中间区域 (4,5,6,7) -> 位置 (2,3,4,5)
            if (families == 0 && (mask & 60) == 0) {  // 60 = 111100
                families = 1;
            }
            result += families;
        }
        
        // 未出现在预订列表中的行，每行2个家庭
        result += (n - rowMask.Count) * 2;
        
        return result;
    }
}

var maxNumberOfFamilies = function(n, reservedSeats) {
    const reservedByRow = new Map();
    
    for (const [row, seat] of reservedSeats) {
        if (!reservedByRow.has(row)) {
            reservedByRow.set(row, new Set());
        }
        reservedByRow.get(row).add(seat);
    }
    
    let result = 0;
    
    // Count families in rows without any reservations
    result += (n - reservedByRow.size) * 2;
    
    // Count families in rows with reservations
    for (const [row, reserved] of reservedByRow) {
        let families = 0;
        
        // Check if seats 2,3,4,5 are available (left group)
        if (!reserved.has(2) && !reserved.has(3) && !reserved.has(4) && !reserved.has(5)) {
            families++;
        }
        
        // Check if seats 6,7,8,9 are available (right group)
        if (!reserved.has(6) && !reserved.has(7) && !reserved.has(8) && !reserved.has(9)) {
            families++;
        }
        
        // If no families found yet, check middle group 4,5,6,7
        if (families === 0 && !reserved.has(4) && !reserved.has(5) && !reserved.has(6) && !reserved.has(7)) {
            families = 1;
        }
        
        result += families;
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

指标复杂度
时间复杂度O(m)，其中 m 是 reservedSeats 的长度
空间复杂度O(k)，其中 k 是有预订座位的行数，最多为 min(m, 10^4)

相关题目