Leetcode 1386:安排电影院座位(超详细的解法!!!)
in leetcode with 0 comment

Leetcode 1386:安排电影院座位(超详细的解法!!!)

in leetcode with 0 comment

如上图所示,电影院的观影厅中有 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

提示:

解题思路

主要存在三种合法区间,分别是[2,5][6,9][4,7]。比较暴力的做法就是将三个区间中的所有元素存储为set,然后遍历reservedSeats将所有同一排的放到同一个set中,最后判断这些set和前面的区间元素是不是有交集。

注意这里有一个边界问题,当有一些行并没有预约座位的时候,我们可以安排两个家庭。也就是当n大于reservedSeats安排的set个数的时候,要将这些遗漏的部分算上。

class Solution:
    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:
        cnt = collections.defaultdict(set)
        for i, j in reservedSeats:
            cnt[i].add(j)
            
        res = 0
        q1 = set([2, 3, 4, 5 ,6, 7, 8, 9])
        q2 = set([2, 3, 4, 5])
        q3 = set([4, 5, 6, 7])
        q4 = set([6, 7, 8, 9])
        for v in cnt.values():
            if len(v & q1) == 0:
                res += 2
            elif len(v & q2) == 0 or len(v & q3) == 0 or len(v & q4) == 0:
                res += 1
        return res + (n - len(cnt)) * 2

上面代码我们是通过set实现的交集操作,由于本题中的每一排座位数很少,所以我们也可以通过位运算实现。

class Solution:
    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:
        cnt = collections.defaultdict(int)
        for i, j in reservedSeats:
            cnt[i] |= 1 << (j - 1)
            
        res = 0
        q1 = int('0111111110', 2)
        q2 = int('0111100000', 2)
        q3 = int('0000011110', 2)
        q4 = int('0001111000', 2)
        for v in cnt.values():
            if v & q1 == 0:
                res += 2
            elif v & q2 == 0 or v & q3 == 0 or v & q4 == 0:
                res += 1
        return res + (n - len(cnt)) * 2

我将该问题的其他语言版本添加到了我的GitHub Leetcode

如有问题,希望大家指出!!!

「如果我的文章对你有很大帮助,那么不妨~!」

coordinate

谢谢老板O(∩_∩)O~

使用微信扫描二维码完成支付

Responses