如上图所示电影院的观影厅中有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^91 reservedSeats.length min(10 * n, 104)reservedSeats[i] [rowi, seati]1 rowi n1 seati 10所有reservedSeats[i]都是互不相同的。分析对于一个家庭而言只有以下三种给他们安排座位的方法安排位置 2345安排位置 4567安排位置 6789。因此每一排的位置 1 和位置 10 都是没有意义的即使被预约了也对答案没有任何影响。从下面的叙述开始我们忽略所有在位置 1 和位置 10 的预约。同时我们可以发现如果一排位置没有被预约那么恰好可以安排给两个家庭即给一个家庭安排位置 2345给另一个家庭安排位置 6789如果一排位置被预约了至少一个座位那么最多只能安排给一个家庭了。用四个变量分别代表 2,34,56,78,9 四个部分被预约的情况分情况讨论这一排能安排的家庭数量分别记录有多少排只能安排一个家庭有多少排一个家庭都安排不了。最后总排数减去这两个值之后乘以2再加上只能安排一个家庭的排数就是答案。class Solution { public: int maxNumberOfFamilies(int n, vectorvectorint reservedSeats) { sort(reservedSeats.begin(),reservedSeats.end()); int lenreservedSeats.size(),cnt[2]{0},rowreservedSeats[0][0],f1,f2,f3,f4;f1f2f3f40; for(int i0;ilen;i) { if(reservedSeats[i][0]row) { if(reservedSeats[i][1]1||reservedSeats[i][1]10)continue; if(reservedSeats[i][1]4reservedSeats[i][1]1f10)f11; else if(reservedSeats[i][1]6reservedSeats[i][1]3f20)f21; else if(reservedSeats[i][1]8reservedSeats[i][1]5f30)f31; else if(reservedSeats[i][1]10reservedSeats[i][1]7f40)f41; } else { // printf(row%d f1%d f2%d f3%d f4%d\n,row,f1,f2,f3,f4); if(f10f20f30f41)cnt[1]; else if(f10f20f31f40)cnt[1]; else if(f10f20f31f41)cnt[1]; else if(f10f21f30f40)cnt[1]; else if(f10f21f30f41)cnt[0]; else if(f10f21f31f40)cnt[0]; else if(f10f21f31f41)cnt[0]; else if(f11f20f30f40)cnt[1]; else if(f11f20f30f41)cnt[1]; else if(f11f20f31f40)cnt[0]; else if(f11f20f31f41)cnt[0]; else if(f11f21f30f40)cnt[1]; else if(f11f21f30f41)cnt[0]; else if(f11f21f31f40)cnt[0]; else if(f11f21f31f41)cnt[0]; f1f2f3f40;rowreservedSeats[i][0],i--; } } printf(row%d f1%d f2%d f3%d f4%d\n,row,f1,f2,f3,f4); if(f10f20f30f41)cnt[1]; else if(f10f20f31f40)cnt[1]; else if(f10f20f31f41)cnt[1]; else if(f10f21f30f40)cnt[1]; else if(f10f21f30f41)cnt[0]; else if(f10f21f31f40)cnt[0]; else if(f10f21f31f41)cnt[0]; else if(f11f20f30f40)cnt[1]; else if(f11f20f30f41)cnt[1]; else if(f11f20f31f40)cnt[0]; else if(f11f20f31f41)cnt[0]; else if(f11f21f30f40)cnt[1]; else if(f11f21f30f41)cnt[0]; else if(f11f21f31f40)cnt[0]; else if(f11f21f31f41)cnt[0]; printf(0%d 1%d\n,cnt[0],cnt[1]); int ans(n-cnt[0]-cnt[1])*2cnt[1]; return ans; } };