1386. Cinema Seat Allocation

题目信息

题号:

1386

难度:

Medium

主题:

位掩码、座位分配、贪心

原题:

LeetCode 1386

重点:

每排十座,四人家庭必须坐在 2-5、4-7 或 6-9;一排最多安排两个家庭

题目重述

电影院有 n 排,每排座位编号 1 到 10。reservedSeats 给出已被预订的位置。一个四人家庭需要四个连续座位,允许的区域是 2-5、4-7 或 6-9。

不同家庭不能共用座位。请返回所有排最多能够安排的四人家庭数量。座位 1 和 10 的预订不影响任何家庭区域。

1 <= n <= 10^9,预订座位数不超过 10^4,位置互不重复。

自建示例

每个受影响排仍可能安排一个家庭:

输入:n = 2, reservedSeats = [[1,2],[1,9],[2,5]]
输出:2
解释:第一排可使用中间 4-7,第二排可使用右侧 6-9。

没有预订时每排安排两个家庭:

输入:n = 3, reservedSeats = []
输出:6
解释:每排使用 2-5 和 6-9 两个互不重叠区域。