C++ 中的最大电影院座位分配

在本文中，您将学习如何在 C++ 中找到最大的电影院座位分配。

概述

提供给您的是一个拥有多排座位和每排固定数量座位的电影院。每排有 N 个座位，并且位置都是连续的。限制是每个家庭需要 4 个相邻座位，您必须安排座位，以便能够容纳最多的人数。

为方便起见，

• 一排中的座位编号从 1 到 N。
• 每个家庭正好占用 4 个座位。
• 有些座位可能已经被占用或预留，这意味着一个家庭不能坐在那里。
• 问题是找出所有排中可以容纳的最大家庭数量。

方法

这个问题可以使用高效的算法来解决，以计算最大的家庭数量。主要考虑因素是

1. 识别座位块：将行分成可用的 4 个连续座位部分。
2. 限制：已占用或预留的座位，这限制了可能的家庭安置。
3. 优化安置：贪婪地将家庭分配到有效的部分。

输入格式

1. R：行数。
2. N：每行的座位数。
3. B：被占用的座位数。
4. 被占用的座位列表，其中每个条目指定行和座位索引。

算法

1. 数据表示：它将每行表示为向量或位掩码，以快速识别被占用的座位和空闲区域。
2. 有效座位配置
   • 如果索引为 (x, x+1, x+2, x+3) 的四个座位均未被占用，则一个家庭可以坐在这些座位上。
   • 如果 N < 4，则无法安排任何家庭入座。
3. 遍历行
   对于每行，计算
   • 有效 4 座组的总数。
   • 确保被占用的座位不与这些组重叠。
4. 优化
   • 使用位掩码更快地检查连续的空闲座位。
   • 对于每行，尝试最大化家庭数量。
5. 输出：所有行中可容纳的家庭总数。

示例

让我们举一个例子来说明 C++ 中的最大影院座位分配。

输出

输入

输出

Maximum number of families that can be seated: 6   

代码解释

1. 数据结构:
   • unordered_map<int, set<int>>: 它存储每行的被占用座位。
   • vector<int>: 它表示每行的座位安排，用于标记空闲和被占用的座位。
2. 关键函数
   • maxFamiliesInRow：它根据被占用的座位计算一行中可容纳的最大家庭数量。
   • maxCinemaFamilies：它遍历所有行并汇总各行中的最大家庭数量。
3. 输入/输出
   • 输入：行数、每行的座位数以及被占用的座位位置。
   • 输出：可容纳的最大家庭数量。

复杂度分析

1. 时间复杂度
   • 遍历行：O(R)O(R)O(R)。
   • 处理一行的被占用座位：O(B)O(B)O(B)（用于集合操作）。
   • 检查配置：O(N)O(N)O(N)。
   • 总计：O(R+B+N)O(R + B + N)O(R+B+N)。
2. 空间复杂度
   • 被占用座位的存储：O(B)O(B)O(B)。
   • 按行存储座位状态：O(N)O(N)O(N)。
   • 总计：O(B+N)O(B + N)O(B+N)。

示例演练

输入

• 行数：R=3R = 3R=3
• 每行座位数：N=10N = 10N=10
• 被占用座位：B=4B = 4B=4（位置：(1, 4), (1, 5), (2, 2), (3, 9)）

输出

最大家庭数 = 444

说明

1. 第 1 行：被占用座位 (4, 5) 阻止了中间区域的家庭。左侧和右侧区域可用 → 222 个家庭。
2. 第 2 行：被占用座位 (2) 不影响座位安排。左侧和右侧区域均空闲 → 222 个家庭。
3. 第 3 行：被占用座位 (9) 影响右侧区域。只有左侧区域空闲 → 111 个家庭。总家庭数 = 2+2+1=42 + 2 + 1 = 42+2+1=4。

优化

1. 位掩码：使用位掩码而不是将行存储为向量，以实现高效的空间和时间。
2. 并行处理：行是独立的；计算可以并行化。
3. 提前终止：如果某行有太多被占用的座位，则跳过不必要的检查。

结论

总之，该解决方案描述了一种高效且可扩展的 C++ 算法，用于解决“最大影院座位分配”问题。模块化设计与仔细优化相结合，确保该程序能够高效处理实际限制，例如大型座位安排和数百个被占用的座位。