1606: 星际列车的座位
Memory Limit:128 MB
Time Limit:1.000 S
Judge Style:Text Compare
Creator:
Submit:26
Solved:4
Description
小明设计了星际宽体列车的座位如下图示。长长的列车共有n排座位,每一排共有10个座位,编号从1到10。
给你 m个数的数组 seats的数据 ,包含所有已经被预约了的 m个座位。比如说,seats[i]=[3 8]
,它表示第 3 排第 8 个座位被预约了。
请你返回 最多能安排多少个 4 人家庭 。4 人家庭要占据 同一排内连续 的 4 个座位。隔着过道的座位(比方说 [3,3] 和 [3,4])不是连续的座位,但是如果你可以将 4 人家庭拆成过道两边各坐 2 人,这样子是允许的。
示例 1:
输入:n = 3 reservedSeats = [[1 2][1 3][1 8][2 6][3 1][3 10]]
输出:4 解释:上图所示是最优的安排方案,总共可以安排 4 个家庭。蓝色的叉表示被预约的座位,橙色的连续座位表示一个 4 人家庭。
Input
输入第一行为 n 与 m , n为列车有 n排座位,m为己被预约的座位数。其后m行,每行两个数,前一数为己预约的排教,后一数为座位号。数字间空一格。
Output
输出一个正整数,为最多能安排 4人家庭的数目。
Sample Input Copy
3 6
1 2
1 3
1 8
2 6
3 1
3 10
Sample Output Copy
4
HINT
-
1 <= n <= 10^9; 1=< m <=10^6