题目大意：
安排电影院座位
如上图所示，电影院的观影厅中有 n 行座位，行编号从 1 到 n ，且每一行内总共有 10 个座位，列编号从 1 到 10 。
给你数组 reservedSeats ，包含所有已经被预约了的座位。比如说，researvedSeats[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 人家庭。
示例 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, 10^4)
- reservedSeats[i].length == 2
- 1 <= reservedSeats[i][0] <= n
- 1 <= reservedSeats[i][1] <= 10
- 所有 reservedSeats[i] 都是互不相同的。
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1386
解题思路分析：
首先我们应该明确一点，一行最多能安排2组合理的4人家庭，也就是说最优情况是2-5列安排一组，6-9列安排一组。除此之外的情况下，当前行最多只可以安排一组，2-5列或是4-7列亦或是6-9列。
解题时，初始默认每一行的2-5列，4-7列，6-9列是可以安排座位的。按照当前座位的列数，会出现如下几种情况：
- 如果当前座位在第2列或者第3列，设置2-5列不能安排连坐。
- 如果当前座位在第4列或者第5列，设置2-5列不能安排连坐，并且4-7列不能安排连坐
- 如果当前座位在第6列或者第7列，设置4-7列不能安排连坐，并且6-9列不能安排连坐
- 如果当前座位在第8列或者第9列，设置6-9列不能安排连坐。
我们先将 reservedSeats 数组按照行数进行排序，然后开始循环数组中每一个已选座位，另外在循环时我们将所有数组中所有已选座位按照行数来进行分组，由于数组已经排序，因此相同行数的数据会连续出现，当下一个座位的行数与当前座位行数不同时，或者当前座位是数组最后一个元素时，代表当前行所有已选座位都已经循环完，这时按照上面的规则，我们可知2-5列，4-7列，6-9列这三组的可选情况，如果2-5列与6-9列能同时安排座位，那么返回结果加2。反之如果2-5列，4-7列，6-9列任意一组可以安排座位，返回结果加一。
另外，当行数发生改变时，当前行与下一行之间可能会有n行的间隔，这n行应是没有已选座位的行，这些行都是可以安排两组家庭的行。最后还不要忘记已选座位中最小行数减一到第1行之间也是没人的座位，这些行同样可以安排2组家庭。
实现代码：
public int maxNumberOfFamilies(int n, int[][] reservedSeats) {
Arrays.sort(reservedSeats,(a,b)->a[0]-b[0]);
int res=(reservedSeats[0][0]-1)*2;
boolean canSitRight=true,canSitMiddle=true,canSitLeft=true;
for(int i=0;i<reservedSeats.length;i++){
int[] s=reservedSeats[i];
if(s[1]==2||s[1]==3){
canSitLeft=false;
}else if(s[1]==4||s[1]==5){
canSitLeft=false;
canSitMiddle=false;
}else if(s[1]==6||s[1]==7){
canSitMiddle=false;
canSitRight=false;
}else if(s[1]==8||s[1]==9){
canSitRight=false;
}
if(i<reservedSeats.length-1&&reservedSeats[i+1][0]!=s[0]
|| i==reservedSeats.length-1){
if(i==reservedSeats.length-1){
res+=(n-s[0])*2;
}else{
res+=(reservedSeats[i+1][0]-s[0]-1)*2;
}
if(canSitRight&&canSitLeft) res+=2;
else if(canSitRight||canSitMiddle||canSitLeft)res+=1;
canSitRight=true;
canSitMiddle=true;
canSitLeft=true;
}
}
return res;
} 本题解法执行时间为31ms。
Runtime: 31 ms, faster than 37.69% of Java online submissions for Cinema Seat Allocation.
Memory Usage: 45.3 MB, less than 100.00% of Java online submissions for Cinema Seat Allocation.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-1386-cinema-seat-allocation-解题思路分析/