企业官网建设流程全解析

如上图所示，电影院的观影厅中有n行座位，行编号从 1 到n，且每一行内总共有 10 个座位，列编号从 1 到 10 。

给定一个二维数组reservedSeats，其中reservedSeats[i] = [rowi, seati]表示第rowi行的座位seati已经被预定。

四人小组必须被安排在同一排的四个座位上。该小组可以坐在以下座位块之一：

• 座位2, 3, 4, 5
• 座位4, 5, 6, 7
• 座位6, 7, 8, 9

只有当该块中的所有座位都没有被预订时，才能使用该块。每个座位最多只能分配给一个小组。

返回一个整数，表示可以分配的最大四人小组数量。

示例 1：

输入：n = 3, reservedSeats = [[1,2],[1,3],[1,8],[2,6],[3,1],[3,10]]输出：4解释：上图所示是最优的安排方案，总共可以安排 4 个家庭。蓝色的叉表示被预约的座位，橙色的连续座位表示一个 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, 104)
• reservedSeats[i] == [rowi, seati]
• 1 <= rowi <= n
• 1 <= seati <= 10
• 所有reservedSeats[i]都是互不相同的。

分析：对于一个家庭而言，只有以下三种给他们安排座位的方法：

安排位置 2，3，4，5；
安排位置 4，5，6，7；
安排位置 6，7，8，9。
因此每一排的位置 1 和位置 10 都是没有意义的，即使被预约了也对答案没有任何影响。从下面的叙述开始，我们忽略所有在位置 1 和位置 10 的预约。同时我们可以发现，如果一排位置没有被预约，那么恰好可以安排给两个家庭，即给一个家庭安排位置 2，3，4，5，给另一个家庭安排位置 6，7，8，9；如果一排位置被预约了至少一个座位，那么最多只能安排给一个家庭了。

用四个变量，分别代表 2,3；4,5；6,7；8,9 四个部分被预约的情况，分情况讨论这一排能安排的家庭数量，分别记录有多少排只能安排一个家庭，有多少排一个家庭都安排不了。最后总排数减去这两个值之后乘以2，再加上只能安排一个家庭的排数就是答案。

class Solution { public: int maxNumberOfFamilies(int n, vector<vector<int>>& reservedSeats) { sort(reservedSeats.begin(),reservedSeats.end()); int len=reservedSeats.size(),cnt[2]={0},row=reservedSeats[0][0],f1,f2,f3,f4;f1=f2=f3=f4=0; for(int i=0;i<len;++i) { if(reservedSeats[i][0]==row) { if(reservedSeats[i][1]==1||reservedSeats[i][1]==10)continue; if(reservedSeats[i][1]<4&&reservedSeats[i][1]>1&&f1==0)f1=1; else if(reservedSeats[i][1]<6&&reservedSeats[i][1]>3&&f2==0)f2=1; else if(reservedSeats[i][1]<8&&reservedSeats[i][1]>5&&f3==0)f3=1; else if(reservedSeats[i][1]<10&&reservedSeats[i][1]>7&&f4==0)f4=1; } else { // printf("row=%d f1=%d f2=%d f3=%d f4=%d\n",row,f1,f2,f3,f4); if(f1==0&&f2==0&&f3==0&&f4==1)cnt[1]++; else if(f1==0&&f2==0&&f3==1&&f4==0)cnt[1]++; else if(f1==0&&f2==0&&f3==1&&f4==1)cnt[1]++; else if(f1==0&&f2==1&&f3==0&&f4==0)cnt[1]++; else if(f1==0&&f2==1&&f3==0&&f4==1)cnt[0]++; else if(f1==0&&f2==1&&f3==1&&f4==0)cnt[0]++; else if(f1==0&&f2==1&&f3==1&&f4==1)cnt[0]++; else if(f1==1&&f2==0&&f3==0&&f4==0)cnt[1]++; else if(f1==1&&f2==0&&f3==0&&f4==1)cnt[1]++; else if(f1==1&&f2==0&&f3==1&&f4==0)cnt[0]++; else if(f1==1&&f2==0&&f3==1&&f4==1)cnt[0]++; else if(f1==1&&f2==1&&f3==0&&f4==0)cnt[1]++; else if(f1==1&&f2==1&&f3==0&&f4==1)cnt[0]++; else if(f1==1&&f2==1&&f3==1&&f4==0)cnt[0]++; else if(f1==1&&f2==1&&f3==1&&f4==1)cnt[0]++; f1=f2=f3=f4=0;row=reservedSeats[i][0],i--; } } printf("row=%d f1=%d f2=%d f3=%d f4=%d\n",row,f1,f2,f3,f4); if(f1==0&&f2==0&&f3==0&&f4==1)cnt[1]++; else if(f1==0&&f2==0&&f3==1&&f4==0)cnt[1]++; else if(f1==0&&f2==0&&f3==1&&f4==1)cnt[1]++; else if(f1==0&&f2==1&&f3==0&&f4==0)cnt[1]++; else if(f1==0&&f2==1&&f3==0&&f4==1)cnt[0]++; else if(f1==0&&f2==1&&f3==1&&f4==0)cnt[0]++; else if(f1==0&&f2==1&&f3==1&&f4==1)cnt[0]++; else if(f1==1&&f2==0&&f3==0&&f4==0)cnt[1]++; else if(f1==1&&f2==0&&f3==0&&f4==1)cnt[1]++; else if(f1==1&&f2==0&&f3==1&&f4==0)cnt[0]++; else if(f1==1&&f2==0&&f3==1&&f4==1)cnt[0]++; else if(f1==1&&f2==1&&f3==0&&f4==0)cnt[1]++; else if(f1==1&&f2==1&&f3==0&&f4==1)cnt[0]++; else if(f1==1&&f2==1&&f3==1&&f4==0)cnt[0]++; else if(f1==1&&f2==1&&f3==1&&f4==1)cnt[0]++; printf("0=%d 1=%d\n",cnt[0],cnt[1]); int ans=(n-cnt[0]-cnt[1])*2+cnt[1]; return ans; } };