X

LEETCODE 1386. Cinema Seat Allocation 解题思路分析

题目大意:

安排电影院座位

如上图所示,电影院的观影厅中有 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列是可以安排座位的。按照当前座位的列数,会出现如下几种情况:

  1. 如果当前座位在第2列或者第3列,设置2-5列不能安排连坐。
  2. 如果当前座位在第4列或者第5列,设置2-5列不能安排连坐,并且4-7列不能安排连坐
  3. 如果当前座位在第6列或者第7列,设置4-7列不能安排连坐,并且6-9列不能安排连坐
  4. 如果当前座位在第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-解题思路分析/
Categories: leetcode
kwantong: