LeetCode1386.CinemaSeatAllocation安排电影院座位【Medium】【Python】【哈希表】问题LeetCodeAcinemahasnrowsseats,numbersfrom1tonandthereare每行10个座位，如上图所示从1到10标记。给定数组reservedSeats包含已预订的座位数，例如reservedSeats[i]=[3,8]表示位于第3行的座位标有8的已被保留。返回您可以在电影院座位上分配的四人家庭的最大数量。一个四口之家占据一排四个座位，彼此相邻。跨过道的座位（例如[3,3]和[3,4]）不被认为是相邻的，但是，四人家庭被过道隔开是允许的，但在那个例1：输入：n=3,reservedSeats=[[1,2],[1,3],[1,8],[2,6],[3,1],[3,10]]输出：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,10^4)reservedSeats[i].length==21<=reservedSeats[i][0]<=n1<=reservedSeats[i][1]<=10AllreservedSeats[i]是不同的。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户家庭。蓝色十字代表预留座位，橙色连续座位代表一家四口。示例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,10^4)reservedSeats[i].length==21<=reservedSeats[i][0]<=n1<=reservedSeats[i][1]<=10所有reservedSeats[i]彼此不同。想法哈希表在正面考虑时容易超时/内存过大，但可以从负面考虑。统计预定的座位，然后反向过滤可以坐的座位。输入importListclass解决方案的Python3代码：defmaxNumberOfFamilies(self,n:int,reservedSeats:List[List[int]])->int:left,right,mid=set(),set(),set()count=0#计算r,c在reservedSeats中的预留席位：如果r在左，r在右，r在中：继续ifc<6andc>1:left.add(r)ifc<10andc>5:right.add(r)ifc<8andc>3:mid.add(r)foriin(left|right|mid):#reservationpositionisonboths:1or10ifinotinleftandinotinright:count+=2#约会位置在左/右：2or3or8or9elifinotinmid:count+=1#约会位置在中间：4or5or6or7elifinotinleftorinotinright:count+=1#反向过滤，未保留的行最多可容纳两个家庭count+=2*(n-len(left|right|mid))returnncountGitHublinkPython参考Python反向过滤
