请用python写出完整代码:电影院的观影厅中有 n 行座位,行编号从 1 到 n ,且每一行 内总共有 10 个座位,列编号从 1 到 10 。 给你数组 reservedSeats ,包含所有已经被预约了的座位。比如说, researvedSeats[i]=[3,8] ,它表示第 3 行第 8 个座位被预约了。 请你返回 最多能安排多少个 4 人家庭 。4 人家庭要占据 同一行内连续 的 4 个座位。 隔着过道的座位(比方说 [3,3] 和 [3,4])不是连续的座位,但是如果你可以将 4 人家 庭拆成过道两边各坐 2 人,这样子是允许的。
时间: 2024-03-01 13:55:36 浏览: 132
毕业设计,基于SSM+MyBatis+MySql+Bootstrap开发的电影院订票系统,内含Java完整源代码,数据库脚本
以下是一个用哈希表解决电影院座位预约问题的Python代码:
```python
def maxNumberOfFamilies(n, reservedSeats):
# 初始化哈希表
seat_map = {}
for row in reservedSeats:
if row[0] not in seat_map:
seat_map[row[0]] = [0] * 10
seat_map[row[0]][row[1]-1] = 1
# 统计可用座位
count = 0
for row in seat_map:
# 判断是否有连续的四个座位
if all(seat_map[row][i] == 0 for i in range(1, 9)):
count += 2
elif all(seat_map[row][i] == 0 for i in range(1, 6)):
count += 1
elif all(seat_map[row][i] == 0 for i in range(3, 10)):
count += 1
else:
# 判断是否有两个连续的三个座位
if all(seat_map[row][i] == 0 for i in range(1, 5)) and all(seat_map[row][i] == 0 for i in range(6, 10)):
count += 1
return count
# 示例
print(maxNumberOfFamilies(3, [[1,2],[1,3],[1,8],[2,6],[3,1],[3,10]])) # 输出 4
```
该算法的时间复杂度为 O(n),其中 n 是座位行数。
阅读全文