A cinema has n rows of seats, numbered from 1 to n and there are ten seats in each row, labelled from 1 to 10 as shown in the figure above.
Given the array reservedSeats containing the numbers of seats already reserved, for example, reservedSeats[i] = [3,8] means the seat located in row 3 and labelled with 8 is already reserved.
Return the maximum number of four-person groups you can assign on the cinema seats. A four-person group occupies four adjacent seats in one single row. Seats across an aisle (such as [3,3] and [3,4]) are not considered to be adjacent, but there is an exceptional case on which an aisle split a four-person group, in that case, the aisle split a four-person group in the middle, which means to have two people on each side.
 
Example 1:

Input: n = 3, reservedSeats = [[1,2],[1,3],[1,8],[2,6],[3,1],[3,10]]
Output: 4
Explanation: The figure above shows the optimal allocation for four groups, where seats mark with blue are already reserved and contiguous seats mark with orange are for one group.

Example 2:
Input: n = 2, reservedSeats = [[2,1],[1,8],[2,6]]
Output: 2

Example 3:
Input: n = 4, reservedSeats = [[4,3],[1,4],[4,6],[1,7]]
Output: 4

 
Constraints:

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
All reservedSeats[i] are distinct.

Difficulty: interview

Starter code:

class Solution:
    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:
        

Solutions:
class Solution:
    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:
        left, right, mid = set(), set(), set()
        count = 0
        for row, col in reservedSeats:
  
            # if row in left and row in right and row in mid:
            #     continue
            if col < 6 and col > 1:
                left.add(row)
            if col < 10 and col > 5:
                right.add(row)
            if col < 8 and col > 3:
                mid.add(row)
        for i in (left | right | mid):
            if i not in mid:
                count += 1
            elif i not in left or i not in right:
                count += 1
        count += 2 * (n - len(left | right | mid))
        return count

class Solution:
    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:
        masks = {}
        
        for row, col in reservedSeats:
            masks[row] = masks.get(row, 0) + (1 << (10 - col))
        
        cnt = 2 * (n - len(masks))
        
        dbl_mask1, dbl_mask2 = 0b0111100000, 0b0000011110
        mdl_mask = 0b0001111000
        
        for row, mask in masks.items():
            cur = max(int((mask & dbl_mask1) == 0) + int((mask & dbl_mask2) == 0),
                      int((mask & mdl_mask) == 0))
            cnt += cur
        return cnt

class Solution:
    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:
        rowHash = dict()
        numGroups = 0
        
        for res in reservedSeats:
            if res[0] in rowHash:
                rowHash[res[0]][res[1]] = True
            else:
                rowHash[res[0]] = dict()
                rowHash[res[0]][res[1]] = True
        
        for row in rowHash:
            # print(\"curr row \" + str(row) + \": \" + str(rowHash[row]))
            currGroups = 0

            if 2 not in rowHash[row] and \\
                3 not in rowHash[row] and \\
                4 not in rowHash[row] and \\
                5 not in rowHash[row]:
                currGroups += 1

            if 6 not in rowHash[row] and \\
                7 not in rowHash[row] and \\
                8 not in rowHash[row] and \\
                9 not in rowHash[row]:
                currGroups += 1

            if currGroups == 0 and \\
                4 not in rowHash[row] and \\
                5 not in rowHash[row] and \\
                6 not in rowHash[row] and \\
                7 not in rowHash[row]:
                currGroups += 1

            numGroups += currGroups

            # numGroups += int((nextSeat - currSeat - 1) / 4)
            # print(\"-> num groups:\" + str(numGroups))
        
        return numGroups + 2 * (n - len(rowHash))
        
\"\"\"
BCR: O(n)

Test cases:
n = 2, reservedSeats = [[2,1], [1,8], [2,6]]
- Only care about rows
- Sort it by row, then by seat # (O(klogk), where k is # of reservations)
[[1,8], [2,1], [2,6]]


n = 3
rowHash:    [1:[0,8,11], 2:[0, 1, 6, 11]]
row:        1
numGroups:  0 -> 1 -> 2 -> 3 -> 5

Approach:
- Brute force - reserve entire matrix 10 x n, populate reservations, iterate over each seat, finding chunks of 4 and marking them as reserved as we count. O(10n + k) where n is num rows and k is num reservations
- Sorted reservations
    - For each row without reservations, add int(10 / GROUP_SIZE=4)
    - For each row with reservations, iterate over each seat and calculate number of seats
    - Optimizations:
        - instead of sorting, use a hash map for rows
        - Need to track rows with and without any reservations (also use a heap?)
            - Otherwise cost for finding empty rows is O(n). this overhead is acceptable

\"\"\"

class Solution:
    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:
        
        if not reservedSeats:
            return 2*n
        
        row_reservations = dict()
        
        for reservation in reservedSeats:
            
            row = reservation[0]
            seat = reservation[1]
            
            if seat==1 or seat==10:
                continue
            
            if row not in row_reservations:
                row_reservations[row] = {seat}
            else:
                row_reservations[row].add(seat)
            
        total_families = 2*(n-len(row_reservations))
    
        def lesser_two_fam(rev_res):
            
            fam_count = 0
            
            for row in list(rev_res.values()):
                pos1=1
                pos2=1
                pos3=1
                
                if 2 in row or 3 in row:
                    pos1 = 0
                if 4 in row or 5 in row:
                    pos1 = 0
                    pos2 = 0
                if 6 in row or 7 in row:
                    pos2 = 0
                    pos3 = 0 
                if 8 in row or 9 in row:
                    pos3= 0
                    
                fam_count+= max(pos1,pos2,pos3)
                
            return fam_count
        total_families += lesser_two_fam(row_reservations)
        
        return total_families
        
        
        

            
        
        


class Solution:
    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:
        seatOcc = set()
        rowsOcc = set()
        for i, j in reservedSeats:
            seatOcc.add((i-1, j-1))
            rowsOcc.add(i-1)
        
        count = 2 * (n - len(rowsOcc))
        for i in rowsOcc:
            left = (i,1) not in seatOcc and (i,2) not in seatOcc and (i,3) not in seatOcc and (i,4) not in seatOcc
            mid = (i,3) not in seatOcc and (i,4) not in seatOcc and (i,5) not in seatOcc and (i,6) not in seatOcc
            right = (i,5) not in seatOcc and (i,6) not in seatOcc and (i,7) not in seatOcc and (i,8) not in seatOcc
            
            if(left and right):
                count += 2
            elif(left or mid or right):
                count += 1
        
        return count


class Solution:
    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:
        d={}
        groups=[{2,3,4,5},{4,5,6,7},{6,7,8,9}]
        for x,y in reservedSeats:
            if(x in d):
                d[x].append(y)
            else:
                d[x]=[y]
        ans=0
        for v in d.keys():
            res=set(d[v])
            c=\"\"
            for g in groups:
                if(not(g&res)):
                    c+=\"1\"
                else:
                    c+=\"0\"
            if(int(c,2)==0):
                ans+=0
            elif(int(c,2)==5 or int(c,2)==7):
                ans+=2
            else:
                ans+=1
        return ans+2*(n-len(d))
    

class Solution:
    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:
        
        # fams = n*2
        res = {}
        for seat in reservedSeats:
            row, seat_n = seat
            if row in res:
                res[row].append(seat_n)
            else:
                res[row] = [seat_n]
        fams = 0
        for row in list(res.keys()):
            if len(res[row]) == 1: #only one seat taken
                seat_n = res[row][0]
                if seat_n in [1,10]:
                    fams += 2
                else:
                    fams += 1
            else: #multiple seats taken 
                curr_row = [True for i in range(10)]
                for s in res[row]:
                    curr_row[s-1] = False
                edges = False
                if  sum(curr_row[1:5]) == 4:
                    edges = True
                    fams += 1
                if  sum(curr_row[5:9]) == 4:
                    edges = True
                    fams += 1
                if not edges and sum(curr_row[3:7]) == 4:
                    fams += 1
        fams += ((n-len(list(res.keys())))*2)
        return fams
                
                
                
                
                    


class Solution:
    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:
        masks = {}
        
        for row, col in reservedSeats:
            masks[row] = masks.get(row, 0) + (1 << (10 - col))
        
        cnt = 2 * (n - len(masks))
        
        dbl_mask1, dbl_mask2 = 0b0111100000, 0b0000011110
        mdl_mask = 0b0001111000
        
        print(cnt)
        print({k: f\"{v:b}\" for k,v in masks.items()})
        for row, mask in masks.items():
            cur = max(int((mask & dbl_mask1) == 0) + int((mask & dbl_mask2) == 0),
                      int((mask & mdl_mask) == 0))
            cnt += cur
        return cnt

'''
Ad-Hoc:
Only following configs are possible:
config1 = {2,3,4,5,6,7,8,9} -> 2 groups
config2 = {2,3,4,5} -> 1 group
config3 = {4,5,6,7} -> 1 group
config4 = {6,7,8,9} -> 1 group
'''
class Solution:
    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:
        
        rowSeats = defaultdict(set)
        occupiedRows = set()
        freeRows = n
        
        for seatRow, seatNum in reservedSeats:
            rowSeats[seatRow].add(seatNum)
            if seatRow not in occupiedRows:
                occupiedRows.add(seatRow)
                freeRows -= 1
            
        config1 = {2,3,4,5,6,7,8,9}
        config2 = {2,3,4,5}
        config3 = {4,5,6,7}
        config4 = {6,7,8,9}
        
        #print(rowSeats, config1.intersection(rowSeats[1]))
        res = freeRows*2
        for row in rowSeats:
            if len(rowSeats[row]) == 0 or not config1.intersection(rowSeats[row]):
                res += 2
            else:
                res += int(not config2.intersection(rowSeats[row]) or not config3.intersection(rowSeats[row]) or not config4.intersection(rowSeats[row]))
        
        return res

class Solution:
    # Process only rows that appear in the input, for other rows you can always allocate seats for two families.
    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:
        res, lookup = 0, collections.defaultdict(list)
        for i, j in reservedSeats:
            lookup[i].append(j - 1)
        for i in list(lookup.keys()):
            used = False
            # available size = 10, starting from 0.
            available = [1 for j in range(10)]
            # print('available = {0}, lookup[i] = {1}'.format(available, lookup[i]))
            for j in lookup[i]:
                available[j] = 0
            for start, end in [(1, 5), (5, 9)]:
                if sum(available[start: end]) == 4:
                # if all(j not in lookup[i] for j in range(start, end)):
                    res += 1
                    used = True
            if not used and sum(available[3:7]) == 4:
            # if not used and all(j not in lookup[i] for j in range(4, 8)):
                res += 1
        res += 2 * (n - len(lookup))
        return res
                    
                    


class Solution:
    def maxNumberOfFamilies(self, n, reservedSeats):
        rows = {}
        for r, c in reservedSeats:
            if r not in rows:
                rows[r] = 0
            rows[r] ^= (1 << c)
        res = 0
        p0 = (1 << 2) ^ (1 << 3) ^ (1 << 4) ^ (1 << 5) 
        p1 = (1 << 6) ^ (1 << 7) ^ (1 << 8) ^ (1 << 9) 
        p2 = (1 << 4) ^ (1 << 5) ^ (1 << 6) ^ (1 << 7) 
        for r in rows:
            f0 = (rows[r] & p0) == 0
            f1 = (rows[r] & p1) == 0
            f2 = (rows[r] & p2) == 0
            if f0 and f1:
                res += 2
            elif f0 or f1 or f2:
                res += 1
        return (n - len(rows)) * 2 + res

class Solution:
    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:
        self.d1 = self.d2 = self.d3 = 0
        reservedSeats = sorted(reservedSeats, key=lambda x:x[0])
        ptr = 0
        i = 0
        ans  = 0
        while i < len(reservedSeats):
            if reservedSeats[i][0] != ptr:
                if self.d1 ^ 15 == 15:
                    ans += 1
                    if self.d3 ^ 15 == 15:
                        ans += 1
                elif self.d2 ^ 15 == 15:
                    ans += 1
                elif self.d3 ^ 15 == 15:
                    ans += 1
                ans += 2 * (reservedSeats[i][0] - ptr - 1)
                self.d1 = self.d2 = self.d3 = 0
                ptr = reservedSeats[i][0]
            self.seat(reservedSeats[i][1])
            i += 1
        
        if self.d1 ^ 15 == 15:
            ans += 1
            if self.d3 ^ 15 == 15:
                ans += 1
        elif self.d2 ^ 15 == 15:
            ans += 1
        elif self.d3 ^ 15 == 15:
            ans += 1
        ans += 2 * (n - ptr)
        
        return ans - 2
                
    def seat(self, i):
        if i == 2 or i == 3:
            self.d1 += 2 ** (i - 2)
        elif i == 4 or i == 5:
            self.d1 += 2 ** (i - 2)
            self.d2 += 2 ** (i - 4)
        elif i == 6 or i == 7:
            self.d2 += 2 ** (i - 4)
            self.d3 += 2 ** (i - 6)
        elif i == 8 or i == 9:
            self.d3 += 2 ** (i - 6)


class Solution:
    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:
        processed = {}
        seatdict = defaultdict(int)
        for i in reservedSeats:
            seatdict[i[0] - 1] += 2**i[1]
        counter = 0
        for i in seatdict:
            seatint = seatdict[i]
            if seatint in processed:
                counter += processed[seatint]
                continue
            else:
                subcounter = 0
                if seatint & (2**4 + 2**5 + 2**6 + 2**7) == 0:
                    subcounter += 1
                    if seatint & (2**2 + 2**3 + 2**8 + 2**9) == 0:
                        subcounter += 1
                else:
                    if seatint &(2**2 + 2**3 + 2**4 + 2**5) == 0: 
                        subcounter += 1
                    elif seatint & (2**6 + 2**7 + 2**8 + 2**9) == 0:
                        subcounter += 1
                processed[seatint] = subcounter
                counter += subcounter
        counter += 2 * (n - len(seatdict))
        return counter  

class Solution:
    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:
        seats = defaultdict(set)
        
        if len(reservedSeats) == 0:
            return 2*n
        
        for seat in reservedSeats:
            row, col = seat
            seats[row].add(col)
            

        
        result = 0
        for i in seats.keys():
            total = 0
            if len({2,3,4,5}.intersection(seats[i])) == 0:
                total += 1
            if len({6,7,8,9}.intersection(seats[i])) == 0:
                total += 1
            if len({4,5,6,7}.intersection(seats[i])) == 0 and total == 0:
                total += 1
            result += total
            
        rowsLeft = n-len(seats)
        result += 2*rowsLeft
            
        return result

from collections import defaultdict
class Solution:
#     def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:
#         reservedSeats.sort()
#         n_res = len(reservedSeats)
#         ans = 2 * n
#         row, res_id = 0, 0
        
#         while res_id < n_res:
#             cur_row = reservedSeats[res_id][0]
            
#             rm = set()
#             while res_id < n_res and reservedSeats[res_id][0] == cur_row:
#                 j = reservedSeats[res_id][1]
#                 if j in (2, 3, 4, 5):
#                     rm.add(0)
#                 if j in (4, 5, 6, 7):
#                     rm.add(1)
#                 if j in (6, 7, 8, 9):
#                     rm.add(2)
#                 res_id += 1
            
#             if len(rm) == 3:
#                 ans -= 2
#             else:
#                 ans -= 1
            
#         return ans
    
    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:
        seats = defaultdict(set)
        
        for i,j in reservedSeats:
            if j in [2,3,4,5]:
                seats[i].add(0)
            if j in [4,5,6,7]:
                seats[i].add(1)
            if j in [6,7,8,9]:
                seats[i].add(2)
        
        res = 2*n
        for i in seats:
            if len(seats[i]) == 3:
                res -= 2
            else:
                res -= 1
        return res

class Solution:
    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:
        seats = sorted(reservedSeats, key=lambda x: x[0])
        a = set([2,3])
        b = set([4,5])
        c = set([6,7])
        d = set([8,9])
        i = 0
        ans = 0
        print(seats)
        seenRows = set()
        while i < len(seats):
            row = seats[i][0]
            r = row
            seenRows.add(row)
            j = i
            left,leftMiddle,rightMiddle,right = True,True,True,True
            while j < len(seats) and seats[j][0] == row:
                if seats[j][1] in a:
                    left = False
                elif seats[j][1] in b:
                    leftMiddle = False
                elif seats[j][1] in c:
                    rightMiddle = False
                elif seats[j][1] in d:
                    right = False
                j += 1
            ans += max(int(leftMiddle and rightMiddle), int(left and leftMiddle) + int(right and rightMiddle))
            i = j
        return ans + (n - len(seenRows))*2
            


class Solution:
    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:
        d = defaultdict(list)
        prev = ans = 0
        for r in reservedSeats:
            d[r[0]].append(r[1])
        
        for k in sorted(d):
            if k!=prev+1: ans+=2*(k-prev-1)
            prev=k
                
        if prev!=n: ans+=2*(n-prev)
        
        def get1row(x):
            if not x or all(i in [1,10] for i in x):
                return 2
            if all(i not in [4,5,6,7] for i in x) or all(i not in [2,3,4,5] for i in x) or all(i not in [6,7,8,9] for i in x):
                return 1
            return 0
        return ans+sum(get1row(d[k]) for k in d)        

class Solution:
    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:
        reserved = dict()
        for r in reservedSeats:
            reserved[r[0]] = reserved.get(r[0], set())
            reserved[r[0]].add(r[1])
            
        # we can fit 2 groups for all rows with no reservations
        ans = 2 * (n - len(reserved.keys()))
        for _, reservations in reserved.items():
            middle = True
            if all([seat not in reservations for seat in [2,3,4,5]]):
                ans += 1
                middle = False
            if all([seat not in reservations for seat in [6,7,8,9]]):
                ans += 1
                middle = False
            if middle and all([seat not in reservations for seat in [4,5,6,7]]):
                ans += 1
        
        return ans

class Solution:
    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:
        res, lookup = 0, collections.defaultdict(set)
        for i, j in reservedSeats:
            lookup[i].add(j)
        for i in list(lookup.keys()):
            used = False
            for start, end in [(2, 6), (6, 10)]:
                if all(j not in lookup[i] for j in range(start, end)):
                    res += 1
                    used = True
            if not used and all(j not in lookup[i] for j in range(4, 8)):
                res += 1
        res += 2 * (n - len(lookup))
        return res
                    
                    


class Solution:
    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:
        dicts = collections.defaultdict(list)
        for r in reservedSeats:
            dicts[r[0]].append(r[1])
            
        res = 0 
        res += 2 * (n - len(dicts))

        for k in list(dicts.keys()):
            left = True
            right = True
            middle = True
            for seat in dicts[k]:
                if (2 <= seat and seat <= 3) or (seat >= 4 and seat <=5):
                    left = False
                    
                if seat >= 8 and seat <= 9 or (seat >= 6 and seat <= 7):
                    right = False
                    
                if seat >= 4 and seat <= 7:
                    middle = False

                
            if left and right and middle:
                res += 2
            elif left or right or middle:
                res += 1
                
        return res
                    
                


class Solution:
    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:
        
        res = 0
        d = dict()
        for seat in reservedSeats:
            if seat[0] in d:
                d[seat[0]].append(seat[1])
            else:
                d[seat[0]] = [seat[1]]

        row = 1
        for k in sorted(d):
            if row < k:
                res += (k - row) * 2
                row = k + 1
            elif row == k:
                row += 1
            
            centre_occ = False
            if not any(s in d[k] for s in (2,3,4,5)):
                res += 1
                centre_occ = True
            if not any(s in d[k] for s in (6,7,8,9)):
                res += 1
                centre_occ = True
            
            if not centre_occ and not any(s in d[k] for s in (4,5,6,7)):
                res += 1
        
        if row <= n:
            res += (n+1-row) * 2
        return res

class Solution:
    def maxNumberOfFamilies(self, n: int, r: List[List[int]]) -> int:
        r=sorted(r)
        l=[0 for i in range(10)]
        ans=0
        n_occ=0
        r.append([0,0])
        for i in range(0,len(r)):
            if i==0:
                l[r[0][1]-1]=1
            else:
                if r[i][0]==r[i-1][0]:
                    l[r[i][1]-1]=1
                else:
                    n_occ+=1
                    if (l[1]==0)&(l[2]==0)&(l[3]==0)&(l[4]==0):
                        ans+=1
                        if (l[5]==0)&(l[6]==0)&(l[7]==0)&(l[8]==0):
                            ans+=1
                    elif (l[5]==0)&(l[6]==0)&(l[7]==0)&(l[8]==0):
                        ans+=1
                    elif (l[3]==0)&(l[4]==0)&(l[5]==0)&(l[6]==0):
                        ans+=1
                    #print(r[i],l)
                    l=[0 for i in range(10)]   
                    l[r[i][1]-1]=1
        ans+=(n-n_occ)*2
        return ans

class Solution:
    def maxNumberOfFamilies(self, n: int, reserved: List[List[int]]) -> int:
        reserved.sort()
        result = 2 * n
        state = [1, 1, 1]
        for idx, (row, col) in enumerate(reserved):
            if idx > 0 and row != reserved[idx-1][0]:
                if not state[0] or not state[2]:
                    result -= 1
                    if not any(state):
                        result -= 1
                state = [1, 1, 1]                        
            if col in range(2, 6):
                state[0] = 0
            if col in range(4, 8):
                state[1] = 0
            if col in range(6, 10):
                state[2] = 0
        if not state[0] or not state[2]:
            result -= 1
            if not any(state):
                result -= 1                
        return result

class Solution:
    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:
        rowseats = defaultdict(list)
        for s in reservedSeats:
            rowseats[s[0]].append(s[1])
            
        subtract = 0
        for _, seats in rowseats.items():
            left = True
            right = True
            middle = True
            for s in seats:
                if 2 <= s <= 5:
                    left = False
                if 4 <= s <= 7:
                    middle = False
                if 6 <= s <= 9:
                    right = False
            if left and right:
                subtract += 0
            elif left or right or middle:
                subtract += 1
            else:
                subtract += 2
                
        return n*2 - subtract

class Solution:
    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:
        all_possible_seats = [set([2, 3, 4, 5]), set([4, 5, 6, 7]), set([6, 7, 8, 9])]
        seat_map = collections.defaultdict(set)
        for s in reservedSeats:
            seat_map[s[0]].add(s[1])
        
        count = 0
        for row in seat_map:
            seats_taken = seat_map[row]
            for cand in all_possible_seats:
                if not cand.intersection(seats_taken):
                    count += 1
                    seats_taken = cand.union(seats_taken)
        return count + 2 * (n-len(seat_map.keys()))

class Solution:
    # Process only rows that appear in the input, for other rows you can always allocate seats for two families.
    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:
        res, lookup = 0, collections.defaultdict(set)
        for i, j in reservedSeats:
            lookup[i].add(j)
        for i in list(lookup.keys()):
            used = False
            for start, end in [(2, 6), (6, 10)]:
                if all(j not in lookup[i] for j in range(start, end)):
                    res += 1
                    used = True
            if not used and all(j not in lookup[i] for j in range(4, 8)):
                res += 1
        res += 2 * (n - len(lookup))
        return res
                    
                    


from collections import defaultdict
from bisect import bisect_left

class Solution:
    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:
        answer = 0
        reserved = defaultdict(list)
        for row, col in reservedSeats:
            reserved[row].append(col)
        answer = (n - len(reserved)) * 2
        possibility = [[2, 5], [4, 7], [6, 9]]
        for reserved_seats in reserved.values():
            reserved_seats.sort()
            result = []
            for start, end in possibility:
                idx = bisect_left(reserved_seats, start)
                result.append(1) if idx == len(reserved_seats) or reserved_seats[idx] > end else result.append(0)
            answer += max(result[0] + result[2], result[1])
        return answer

class Solution:
    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:
        lookup = collections.defaultdict(list)
        dic = {}
        for row, seat in reservedSeats:
            if (row - 1) not in lookup:
                data = [0] * 10
                data[seat-1] = 1
                lookup[row-1] = data
            else:
                data = lookup[row-1]
                data[seat-1] = 1
                lookup[row-1] = data
        res = 0            
        print(lookup)
        for k in lookup:
            data_tup = tuple(lookup[k])
            if data_tup not in dic:
                prev = res
                first = third = False
                if lookup[k][1] or lookup[k][2]  or (lookup[k][1] and lookup[k][2]):
                    if sum(lookup[k][3:7]) == 0 or sum(lookup[k][5:9]) == 0:
                        res += 1
                else:
                    #print(i, res)
                    if sum(lookup[k][1:5]) == 0:
                        res += 1
                        first = True
                    if sum(lookup[k][5:9]) == 0:
                        res += 1
                        third = True
                    if not first and not third and sum(lookup[k][3:7]) == 0:
                        res += 1
                    #print(i, res)
                dic[data_tup] = res - prev
            else:
                res += dic[data_tup]
            
            
        return res + 2*(n-len(lookup))

class Solution:
    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:
        left,right,mid = set(), set(), set()
        count = 0
        for row,col in reservedSeats:
            if row in left and row in right and row in mid:
                continue
            if col < 6 and col > 1:
                left.add(row)
            if col < 10 and col > 5:
                right.add(row)
            if col < 8 and col > 3:
                mid.add(row)
        for i in (left|right|mid):
            if i not in mid:
                count += 1
            elif i not in left or i not in right:
                count += 1
        count += 2*(n - len(left|right|mid))
        return count
                    


class Solution:
    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:
        res = 0
        rows = defaultdict(list)
        # store in dict a list of seat numbers for each row:
        for seat in reservedSeats:
            rows[seat[0]].append(seat[1])
     
        for row in rows.keys():
            seat_nums = rows[row]
            
            # if there is only one reserved chair, there are two options:
            if len(seat_nums) == 1:
                res = res+2 if seat_nums[0] in [1, 10] else res+1
    
            else:
\t\t\t\t# help list to find reserved seats in current row:
                help_list = [0]*10
                for seat in seat_nums:
                    help_list[seat-1] = 1
                
                res_copy = res
                if help_list[1:5] == [0,0,0,0]: res+=1
                    
                if help_list[5:9] == [0,0,0,0]: res+=1

                if res_copy == res and help_list[3:7] == [0,0,0,0]: res+=1

        # add two to res for each empty row
        return res + 2 * (n-len(rows.keys()))

class Solution:
    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:
        d, ans = defaultdict(set), 0
        for r,c in reservedSeats:
            d[r].add(c)
        absent = lambda x,s: not any([x in s for x in range(x,x+4)])
        for _,v in list(d.items()):
            ans+= 1+absent(6,v) if absent(2,v) else (absent(4,v) or absent(6,v))
        ans+=2*(n-len(d))
        return ans


class Solution:
    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:
        occ = defaultdict(set)
        for row, col in reservedSeats:
            occ[row].add(col)
        
        ans = 0
        
        for row in occ:
            if all(i not in occ[row] for i in range(2,10)):
                ans+=2
            elif all(i not in occ[row] for i in range(2,6)):
                ans+=1
            elif all(i not in occ[row] for i in range(6,10)):
                ans+=1
            elif all(i not in occ[row] for i in range(4,8)):
                ans+=1
        
        return ans + 2*(n-len(occ))

class Solution:
    # def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:
        # Cinema Seat Allocation 10:24 8/27/20
        
    def countAvailableSeats(self, row, taken_slots):
        if row not in taken_slots:
            return 2          
        if not taken_slots[row][0] and not taken_slots[row][1] and not taken_slots[row][2] and not taken_slots[row][3]:
            return 2
        elif not taken_slots[row][0] and not taken_slots[row][1]:
            return 1
        elif not taken_slots[row][1] and not taken_slots[row][2]:
            return 1
        elif not taken_slots[row][2] and not taken_slots[row][3]:
            return 1                    
        del taken_slots[row]
        return 0
    
    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:            
        # Sort by row to reduce space compexlity to O(1)
        reservedSeats.sort(key=lambda s: s[0]) 
        res, prev_row = 0, 1
        # Allocate four slots - Left (2, 3), Left Center (4, 5), Right Center (6, 7), and Right (8, 9)
        # and mark those four slots as not taken ([False,False,False,False])
        taken_slots = collections.defaultdict(lambda: [False,False,False,False])
        for row, col in reservedSeats:
            if prev_row != row:
                res += 2 * (row - prev_row - 1) # Maximum available slots per empty row is 2
                res += self.countAvailableSeats(prev_row, taken_slots)
            if col in (2, 3):
                taken_slots[row][0] = True
            elif col in (4, 5):
                taken_slots[row][1] = True
            elif col in (6, 7):
                taken_slots[row][2] = True
            elif col in (8, 9):
                taken_slots[row][3] = True
            prev_row = row
            
        # Handle the remaining
        res += 2 * (n - prev_row) # Maximum available slots per empty row is 2
        res += self.countAvailableSeats(prev_row, taken_slots)
        return res
            
        
        
        
        


class Solution:
    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:
        left, right, mid = set(), set(), set()
        count = 0
        for row, col in reservedSeats:
            if col < 6 and col > 1:
                left.add(row)
            if col < 10 and col > 5:
                right.add(row)
            if col < 8 and col > 3:
                mid.add(row)
                
        for i in (left | right | mid):
            if i not in mid or i not in left or i not in right:
                count += 1

        count += 2 * (n - len(left | right | mid))
        return count

class Solution:
    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:
        res=0
        rowDict=collections.defaultdict(int) 
        for r,c in reservedSeats:
          #row=r[0]
          #seatNo=r[1]
            rowDict[r] |=  (1 << (c-1))
        for row in rowDict.values():
            #p1=false, p2=false, p3=false
            print(\"row:\",row)
            p1=not(row & int('0111100000',2))
            p2=not(row & int('0000011110',2))
            p3=not(row & int('0001111000',2))
            print(p1,p2,p3)
            if p1 and p2:
                res+=2;
            elif p1 or p2 or p3:
                res+=1
            else:
                continue
        return res +2 *(n-len(rowDict))

from collections import defaultdict
class Solution:
        
    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:
        i=0
        prev=1
        res=set()
        ans=0
        res = defaultdict(list)
        for i in range(len(reservedSeats)):
            res[reservedSeats[i][0]-1].append(reservedSeats[i][1])
        count_rows=0
        
        helper= [0 for i in range(10)]
        for i in res.keys():
            count_rows+=1
            count=0
            for j in range(10):
                helper[j]=0
            for j in res[i]:
                helper[j-1]=1
            if helper[1:5] == [0,0,0,0]: count+=1
            if helper[5:9] == [0,0,0,0]: count+=1
            if count==0 and helper[3:7] == [0,0,0,0]:
                count+=1
            ans+=count

        ans+=(n-count_rows)*2
        return ans

class Solution:
    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:
        reserved = set()
        rows = set()
        for row, col in reservedSeats:
            reserved.add((row, col))
            rows.add(row)
        count = 2 * (n - len(rows))
        for row in rows:
            for col in [2, 4, 6]:
                if (row, col) not in reserved and (row, col+1) not in reserved and (row, col+2) not in reserved and (row, col+3) not in reserved:
                    #print(reserved, row, col)
                    reserved.add((row, col))
                    reserved.add((row, col+1))
                    reserved.add((row, col+2))
                    reserved.add((row, col+3))
                    #print(row, col)
                    count += 1
        return count

class Solution:
    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:
        reserved_in_row = defaultdict(list)
        for i, j in reservedSeats:
            reserved_in_row[i].append(j)
        res = 2 * (n - len(reserved_in_row))
        for i in reserved_in_row:
            sim = [0 for _ in range(10)]
            for j in reserved_in_row[i]:
                sim[j - 1] = 1
            temp_res = res
            if sim[1: 5] == [0 for _ in range(4)]:
                res += 1
            if sim[5: 9] == [0 for _ in range(4)]:
                res += 1
            if res == temp_res and sim[3: 7] == [0 for _ in range(4)]:
                res += 1
        return res

class Solution:
    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:
        seat_dict = {}
        all_possible_seats = [set([2, 3, 4, 5]), set([4, 5, 6, 7]), set([6, 7, 8, 9])]
        
        for row_seat in reservedSeats:
            row, seat = row_seat
            temp = seat_dict.get(row, [1, 1, 1])
            
            if sum(temp) == 0:
                continue
                
            if seat in all_possible_seats[0]:
                temp[0] = 0
            if seat in all_possible_seats[1]:
                temp[1] = 0
            if seat in all_possible_seats[2]:
                temp[2] = 0
                
            seat_dict[row] = temp
        #print(seat_dict)
        res = 0
        for row, situ in list(seat_dict.items()):
            if situ[1] == 1:
                if situ[0] and situ[2]:
                    res += 2
                else:
                    res += 1
            else:
                if situ[0] or situ[2]:
                    res +=1
            

        
        res += 2*(n-len(list(seat_dict.keys())))
        return res
        


class Solution:
    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:
        hsh = {}
        
        for i in reservedSeats:
            row = i[0] - 1
            seat = i[1] - 1
            
            if row not in hsh:
                hsh[row] = [True for i in range(10)]
                
            hsh[row][seat] = False
            
            
        count = (n - len(hsh))*2
        for row in hsh:
            cnt = 0
            cou = 0
            for i in range(10):
                if hsh[row][i]:
                    
                    if i in (3,7) and cnt % 2 == 1:
                        cnt -= 1
                    cnt += 1
                    if cnt == 4:
                        cou += 1
                        cnt = 0
                else:
                    cnt = 0
            count += cou
                
        return count
                    
                
            
            


class Solution:
    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:
        # Beware of aisle split
        # Only have a few configurations to sit 4 people in a given row
        # 1) [4, 5, 6, 7]
        # 2) [2, 3, 4, 5]
        # 3) [6, 7, 8, 9]
        # 4) (2) AND (3)
        
        
        # Brute force: Walk over all the rows O(n^2), with a map of seatOccupied[row][seat_number] = True
        # Better: Sort reserved seats by row, then seat_number: 2*O(logn)
        # Best: O(n) make a map, O(n) walk over rows
        
        
        occupied = collections.defaultdict(set)
        for reservedSeat in reservedSeats:
            row = reservedSeat[0]
            seat_number = reservedSeat[1]
            
            if seat_number in [4, 5]:
                # Center, Left are occupied
                occupied[row].add(\"C\")
                occupied[row].add(\"L\")
            elif seat_number in [6, 7]:
                # Center, Right are occupied
                occupied[row].add(\"C\")
                occupied[row].add(\"R\")
            elif seat_number in [2, 3]:
                # Left is occupied
                occupied[row].add(\"L\")
            elif seat_number in [8, 9]:
                # Right is occupied
                occupied[row].add(\"R\")
        
        empty_rows: int = n
        total: int = 0
        for row in occupied:
            empty_rows -= 1
            left = \"L\" not in occupied[row]
            right = \"R\" not in occupied[row]
            center = \"C\" not in occupied[row]

            if left and right:
                total += 2
            elif left or right or center:
                total += 1
        
        
        return total + 2 * empty_rows
                
            
            
        
        

class Solution:
    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:
        
        res = 0
        d = dict()
        for seat in reservedSeats:
            if seat[0] in d:
                d[seat[0]].append(seat[1])
            else:
                d[seat[0]] = [seat[1]]

        row = 1
        for k in sorted(d):
            print(\"row {}, krow {}, v {}, res={}\".format(row,k,d[k],res))
            if row < k:
                res += (k - row) * 2
                row = k + 1
            elif row == k:
                row += 1
            
            centre_occ = False
            if not any(s in d[k] for s in (2,3,4,5)):
                res += 1
                centre_occ = True
            if not any(s in d[k] for s in (6,7,8,9)):
                res += 1
                centre_occ = True
            
            if not centre_occ and not any(s in d[k] for s in (4,5,6,7)):
                res += 1
        
        print(\"row {}, n= {}, res={}\".format(row,n,res))
        if row <= n:
            res += (n+1-row) * 2
        return res

class Solution:
    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:
        
        if not reservedSeats:
            return 2*n
        
        row_reservations = dict()
        
        for reservation in reservedSeats:
            
            row = reservation[0]
            seat = reservation[1]
            
            if seat==1 or seat==10:
                continue
            
            if row not in row_reservations:
                row_reservations[row] = {seat}
            else:
                row_reservations[row].add(seat)
            
        total_families = 2*(n-len(row_reservations))
    
    
        for row in list(row_reservations.values()):
            pos1=1
            pos2=1
            pos3=1

            if 2 in row or 3 in row:
                pos1 = 0
            if 4 in row or 5 in row:
                pos1 = 0
                pos2 = 0
            if 6 in row or 7 in row:
                pos2 = 0
                pos3 = 0 
            if 8 in row or 9 in row:
                pos3= 0

            total_families+= max(pos1,pos2,pos3)
                
        
        return total_families
        
        
        

            
        
        


class Solution:
    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:
        seat_dict = {}
        
        for seat in reservedSeats:

            row, col = seat
            temp = seat_dict.get(row, set())
            temp.add(col)
            seat_dict[row] = temp

                
        res = 0
        for row in seat_dict.keys():
            row_situ = seat_dict[row]
            if 4 not in row_situ and \\
               5 not in row_situ and \\
               6 not in row_situ and \\
               7 not in row_situ:
                res += 1
            
                if ((2 not in row_situ) and \\
                   (3 not in row_situ) and \\
                   (8 not in row_situ) and \\
                   (9 not in row_situ)):
                    res += 1
            else:
                if ((2 not in row_situ) and \\
                   (3 not in row_situ) and \\
                   (4 not in row_situ) and \\
                   (5 not in row_situ)):
                    res += 1
                
                if ((6 not in row_situ) and \\
                   (7 not in row_situ) and \\
                   (8 not in row_situ) and \\
                   (9 not in row_situ)):
                    res += 1
        res += 2*(n-len(seat_dict.keys()))
        return res
        
        

class Solution:
    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:
        d, ans = defaultdict(set), 0
        for r,c in reservedSeats:
            d[r].add(c)
        absent = lambda x,s: not any(filter(lambda x: x in s, range(x,x+4)))
        for _,v in d.items():
            ans+= 1+absent(6,v) if absent(2,v) else (absent(4,v) or absent(6,v))
        ans+=2*(n-len(d))
        return ans

class Solution:
    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:
        total=2*n
        
        dicts={}
        
        for k in range(len(reservedSeats)):
            index=reservedSeats[k][0]
            val=reservedSeats[k][1]
            
            if index not in dicts:
                dicts[index]=[1,1,1];
            curr_list=dicts[index]
            maxim=max(curr_list[0]+curr_list[2],curr_list[1])
            if val in [2,3,4,5]:
                curr_list[0]=0
            if val in [4,5,6,7]:
                curr_list[1]=0
            if val in [6,7,8,9]:
                curr_list[2]=0
            dicts[index]=curr_list
            total=total-(maxim-max(curr_list[0]+curr_list[2],curr_list[1]))
        print(dicts)
        return total
        


#
# @lc app=leetcode id=1386 lang=python3
#
# [1386] Cinema Seat Allocation
#
# https://leetcode.com/problems/cinema-seat-allocation/description/
#
# algorithms
# Medium (33.70%)
# Total Accepted:    9K
# Total Submissions: 25.8K
# Testcase Example:  '3\
[[1,2],[1,3],[1,8],[2,6],[3,1],[3,10]]'
#
#
#
# A cinema  has n  rows of seats, numbered from 1 to n  and there are ten  seats in
# each row, labelled from 1  to 10  as shown in the figure above.
#
# Given the array reservedSeats containing the numbers of seats already
# reserved, for example, reservedSeats[i] = [3,8]  means the seat located in row
# 3 and labelled with 8  is already reserved.
#
# Return the maximum number of four-person groups  you can assign on the cinema
# seats. A four-person group  occupies four  adjacent seats in one single row.
# Seats across an aisle (such as [3,3]  and [3,4]) are not considered to be
# adjacent, but there is an exceptional case  on which an aisle split  a
# four-person group, in that case, the aisle split  a four-person group in the
# middle,  which means to have two people on each side.
#
#
# Example 1:
#
#
#
#
# Input: n = 3, reservedSeats = [[1,2],[1,3],[1,8],[2,6],[3,1],[3,10]]
# Output: 4
# Explanation: The figure above shows the optimal allocation for four groups,
# where seats mark with blue are already reserved and contiguous seats mark
# with orange are for one group.
#
#
# Example 2:
#
#
# Input: n = 2, reservedSeats = [[2,1],[1,8],[2,6]]
# Output: 2
#
#
# Example 3:
#
#
# Input: n = 4, reservedSeats = [[4,3],[1,4],[4,6],[1,7]]
# Output: 4
#
#
#
# Constraints:
#
#
# 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
# All reservedSeats[i] are distinct.
#
#
#
from typing import List


def calculate_groups(reserved_array):
    \"\"\"
    >>> calculate_groups([0,0,1,1,0,0,0,0,0,1,0,0])
    1

    >>> calculate_groups([0,0,0,0,0,0,1,0,0,0,0,0])
    1

    >>> calculate_groups([0,1,0,0,0,0,0,0,0,0,0,1])
    2

    \"\"\"
    center_seats = 0
    side_seats = 0
    if sum(reserved_array[4:8]) == 0:
        center_seats += 1
    if sum(reserved_array[2:6]) == 0:
        side_seats += 1
    if sum(reserved_array[6:10]) == 0:
        side_seats += 1
    return max(center_seats, side_seats)

class Solution:
    \"\"\"
    >>> Solution().maxNumberOfFamilies(3, [[1,2],[1,3],[1,8],[2,6],[3,1],[3,10]])
    4

    >>> Solution().maxNumberOfFamilies(2, [[2,1],[1,8],[2,6]])
    2

    >>> Solution().maxNumberOfFamilies(4, [[4,3],[1,4],[4,6],[1,7]])
    4

    \"\"\"

    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:

        reservedSeats = sorted(reservedSeats, key=lambda i: i[0])
        counter = 0
        row = 1
        reserved = [0] * 11
        while reservedSeats:
            item = reservedSeats.pop(0)
            if item[0] != row:
                missed_rows = item[0] - row - 1
                counter += 2 * missed_rows
                counter += calculate_groups(reserved)
                row = item[0]
                reserved = [0] * 11
                reserved[item[1]] = 1
            else:
                reserved[item[1]] = 1
        counter += calculate_groups(reserved)
        counter += (n - row) * 2
        return counter


class Solution:
    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:
        matrix = collections.defaultdict(list)
        for i in range(len(reservedSeats)):
            matrix[reservedSeats[i][0]].append(reservedSeats[i][1])

        res = 2 * n
        for k in matrix:
            cnt = 0
            if 2 not in matrix[k] and 3 not in matrix[k] and 4 not in matrix[k] and 5 not in matrix[k]:
                cnt += 1
            if 6 not in matrix[k] and 7 not in matrix[k] and 8 not in matrix[k] and 9 not in matrix[k]:
                cnt += 1
            if 4 not in matrix[k] and 5 not in matrix[k] and 6 not in matrix[k] and 7 not in matrix[k] and cnt == 0:
                cnt += 1
            res += (cnt - 2)

        return res

class Solution:
    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:
       
        g = defaultdict(int)
        for r, s in reservedSeats: g[r] |= {0: 0, 1: 4, 2: 5, 3: 3, 4: 2, 5: 0}[s >> 1]
        return sum(2 if s == 0 else 1 if s < 7 else 0 for r, s in g.items()) + (n - len(g)) * 2

import collections
class Solution:
    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:
        # lst = [[] for i in range(n)]
        lst = collections.defaultdict(list)
        
        for r, c in reservedSeats:
            lst[r].append(c)
            # lst[r-1].append(c)
        ret = n * 2
        for r in lst:
            flag1 = False
            flag2 = False
            flag3 = False
            for c in lst[r]:
                if 2 <= c <= 5:
                    flag1 = True
                if 6 <= c <= 9:
                    flag2 = True
                if 4 <= c <= 7:
                    flag3 = True
            if flag1:
                ret -= 1
            if flag2:
                ret -= 1
            if (flag1 and flag2) and not flag3:
                ret += 1
        return ret
        # print(lst)


class Solution:
    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:
        reserved = set(tuple(spot) for spot in reservedSeats)
        reserved_rows = set(spot[0] for spot in reservedSeats)
        res = 0
        for row in reserved_rows:
            first = False
            second = False
            third = False
            
            if all((row, col) not in reserved for col in range(2, 6)):
                first = True
            if all((row, col) not in reserved for col in range(4, 8)):
                second = True
            if all((row, col) not in reserved for col in range(6, 10)):
                third = True

            if first and second and third:
                res += 2
            elif first or second or third:
                res += 1
        
        return res + 2*(n - len(reserved_rows))

class Solution:
    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:
        lookup = collections.defaultdict(list)
        dic = {}
        for row, seat in reservedSeats:
            if row - 1 not in lookup:
                data = [0] * 10
                data[seat-1] = 1
                lookup[row-1] = data
            else:
                lookup[row-1][seat-1] = 1
    
        res = 0 
        four_person = [0,0,0,0]
        for k in lookup:
            data_tup = tuple(lookup[k])
            if data_tup not in dic:
                prev = res
                first = third = False
                if lookup[k][1] or lookup[k][2] :
                    if lookup[k][3:7] ==  four_person or lookup[k][5:9] ==  four_person:
                        res += 1
                else:
                    if lookup[k][1:5] == four_person:
                        res += 1
                        first = True
                    if lookup[k][5:9] == four_person:
                        res += 1
                        third = True
                    if not first and not third and lookup[k][3:7] == four_person:
                        res += 1
                dic[data_tup] = res - prev
            else:
                res += dic[data_tup]
            
            
        return res + 2*(n-len(lookup))

import numpy as np
class Solution:
    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:
        d, ans = defaultdict(set), 0
        for r,c in reservedSeats:
            d[r].add(c)
        absent = lambda x,s: not any(filter(lambda x: x in s, range(x,x+4)))
        for _,v in d.items():
            ans+= 1+absent(6,v) if absent(2,v) else (absent(4,v) or absent(6,v))
        ans+=2*(n-len(d))
        return ans

class Solution:
    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:
        from collections import defaultdict
        taken_seats = defaultdict(int)
        for row, col in reservedSeats:
            taken_seats[row] = taken_seats[row] | (1 << (col - 1))
        res = 0
        for seat in taken_seats.values():
            cnt = 0
            if (seat & int('0111100000', 2)) == 0:
                cnt += 1
            if (seat & int('0000011110', 2)) == 0:
                cnt += 1
            # cnt==0 means 2345 and 4567 is not taken respectively
            # and 
            if (seat & int('0001111000', 2)) == 0 and cnt == 0:
                cnt = 1
            res += cnt
        return 2 * (n - len(taken_seats)) + res

class Solution:
    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:
        seated=defaultdict(set)
        for record in reservedSeats:
            seated.setdefault(record[0], set()).add(record[1])
        ans=0
        ans+=(n-len(seated))*2
        for i in seated:
            currentRow=seated[i]
            emptyLeft=2 not in currentRow and 3 not in currentRow
            emptyMidLeft=4 not in currentRow and 5 not in currentRow
            emptyMidRight=6 not in currentRow and 7 not in currentRow
            emptyRight=8 not in currentRow and 9 not in currentRow
            if(emptyLeft and emptyMidLeft and emptyMidRight and emptyRight):
                ans+=2
            elif(emptyLeft and emptyMidLeft):
                ans+=1
            elif(emptyRight and emptyMidRight):
                ans+=1
            elif(emptyMidLeft and emptyMidRight):
                ans+=1
        return ans


class Solution:
    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:
        res = 0
        rows = defaultdict(list)
        #rows = {}
        for seat in reservedSeats:
            #if not rows.get(seat[0]):
                #rows[seat[0]] = [0]*10
            #rows[seat[0]][seat[1]-1] = 1
            rows[seat[0]].append(seat[1])
        print(rows)
        #for i in range(1, n+1):
        for row in list(rows.keys()):
            seat_nums = rows[row]
            #seat_nums = rows.get(i)
            #if not seat_nums:
                #print(f\"nothing in row {i}\")
            #    res+=2
            if len(seat_nums) == 1:
                #if seat_nums[0] == 1 or seat_nums[0] == 10:
                #    res+=2
                #else:
                #    res+=1
                    #print(\"here\")
                res = res+2 if seat_nums[0] in [1, 10] else res+1
    
            else:
                help_list = [0]*10
                for seat in seat_nums:
                    help_list[seat-1] = 1
                
                res_copy = res
                if help_list[1:5] == [0,0,0,0]: res+=1
                    
                if help_list[5:9] == [0,0,0,0]: res+=1

                if res_copy == res and help_list[3:7] == [0,0,0,0]: res+=1

                    
                
        return res + 2*(n-len(list(rows.keys())))


class Solution:
    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:
        res = 0
        rows = defaultdict(list)
        # store in dict a list of seat numbers for each row:
        for seat in reservedSeats:
            rows[seat[0]].append(seat[1])
     
        for row in list(rows.keys()):
            seat_nums = rows[row]
            
            # if there is only one reserved chair, there are two options:
            if len(seat_nums) == 1:
                res = res+2 if seat_nums[0] in [1, 10] else res+1
    
            else:
                help_list = [0]*10
                for seat in seat_nums:
                    help_list[seat-1] = 1
                
                res_copy = res
                if help_list[1:5] == [0,0,0,0]: res+=1
                    
                if help_list[5:9] == [0,0,0,0]: res+=1

                if res_copy == res and help_list[3:7] == [0,0,0,0]: res+=1

        # add two to res for each empty row
        return res + 2 * (n-len(list(rows.keys())))


class Solution:
    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:
        res = 0
        d = defaultdict(set)
        for x,y in reservedSeats: 
            d[x-1].add(y-1)
        for r in d.keys():
            if all(x not in d[r] for x in [1,2,3,4]):
                res += 1
                for x in [1,2,3,4]: d[r].add(x);
            if all(x not in d[r] for x in [3,4,5,6]):
                res += 1
                for x in [3,4,5,6]: d[r].add(x);
            if all(x not in d[r] for x in [5,6,7,8]):
                res += 1
                for x in [5,6,7,8]: d[r].add(x);
        return res + 2 * (n - len(d.keys()))

class Solution:
    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:
        lookup = collections.defaultdict(list)
        dic = {}
        for row, seat in reservedSeats:
            if row - 1 not in lookup:
                data = [0] * 10
                data[seat-1] = 1
                lookup[row-1] = data
            else:
                lookup[row-1][seat-1] = 1
    
        res = 0 
        four_person = [0,0,0,0]
        for data in lookup.values():
            data_tup = tuple(data)
            if data_tup not in dic:
                prev = res
                if data[1:5] == four_person:
                    res += 1
                    if data[5:9] == four_person:
                        res += 1
                elif data[3:7] == four_person or data[5:9] == four_person:
                        res += 1 
                dic[data_tup] = res - prev
            else:
                res += dic[data_tup]
                
        return res + 2*(n-len(lookup))

class Solution(object):
    def maxNumberOfFamilies(self, n, reservedSeats):

        result = 2 * n
        hashtable = {}
        for seat in reservedSeats:
            if seat[0] not in hashtable:
                hashtable[seat[0]] = {seat[1]}
            else:
                hashtable[seat[0]].add(seat[1])
        for item in hashtable:
            counter = 0
            if 2 not in hashtable[item] and 3 not in hashtable[item] and 4 not in hashtable[item] and 5 not in \\
                    hashtable[item]:
                counter += 1
            if 6 not in hashtable[item] and 7 not in hashtable[item] and 8 not in hashtable[item] and 9 not in \\
                    hashtable[item]:
                counter += 1
            if 4 not in hashtable[item] and 5 not in hashtable[item] and 6 not in hashtable[item] and 7 not in \\
                    hashtable[item] and counter == 0:
                counter += 1
            result += (counter - 2)
        return result


class Solution:
    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:
        res = 0
        seats = collections.defaultdict(int)
        for r, seat in reservedSeats:
            seats[r] |= (1 << (seat-1))
        for reserved in list(seats.values()):
            curr = 0
            if (reserved & int('0111100000',2))==0:
                curr += 1
            if (reserved & int('0000011110',2))==0:
                curr += 1
            if (reserved & int('0001111000',2))==0 and curr == 0:
                curr += 1
            res += curr
        return res + 2*(n-len(seats))


from itertools import groupby
from re import finditer

class Solution:
    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:
        ans = 2*n
        reservedSeats.sort()
        rows = groupby(reservedSeats, key=lambda x: x[0])
        for r, c in rows:
            row = ['O']*10
            for _, col in c:
                row[col-1] = 'X'
            row = ''.join(row)
            idx = {f.start() for f in finditer('(?=OOOO)', row)}
            if not idx:
                ans -= 2
            elif 1 in idx and 5 in idx:
                continue
            elif 1 in idx or 3 in idx or 5 in idx:
                ans -= 1
            else:
                ans -= 2
        return ans
    \"\"\"
    OOO OOOO OOO
    OOO OOOO OOO
    \"\"\"

class Solution:
    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:
        \"\"\"
        Runtime: O(m) where m is length of reservedSeats, Space: O(m)
        \"\"\"
        reserved = dict()
        for seat in reservedSeats:
            row, col = seat
            if row not in reserved:
                reserved[row] = {col}
            else:
                reserved[row].add(col)
        
        groups = 2 * n
        for _, cols in reserved.items():
            sections = 0
            if not any(col in cols for col in (2, 3, 4, 5)):
                sections += 1
            if not any(col in cols for col in (6, 7, 8, 9)):
                sections += 1
            # check if sections == 0 to avoid double counting where the sections overlap
            if sections == 0 and not any(col in cols for col in (4, 5, 6, 7)):
                sections += 1
            groups += sections - 2
        return groups
        

class Solution:
    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:
        rows = collections.defaultdict(lambda: [])
        for row, col in reservedSeats:
            rows[row].append(col)
        ans = (n-len(rows))*2
        
        def solveRow(row, pos, memo):
            if pos >= 7:
                return 0
            elif pos in memo:
                return memo[pos]
            
            ret = 0
            if pos in (0, 2, 4, 6) or sum(row[pos: pos+4]) > 0:
                ret = solveRow(row, pos+1, memo)
            else:
                ret = max(solveRow(row, pos+1, memo), 1+solveRow(row, pos+4, memo))
            memo[pos] = ret
            return ret
        
        for row_id in rows:
            row = [0]*10
            for col in rows[row_id]:
                row[col-1] = 1
            ans += solveRow(row, 0, {})
        return ans

class Solution:
    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:
        
        d = {}
        
        for r,c in reservedSeats: #O(M)
            if r not in d:
                d[r] = [1,1,1]
                
            if 2<= c <=5:
                d[r][0] = 0
            if 4 <= c <=7:
                d[r][1] = 0  
            if 6<= c<=9:
                d[r][2] = 0
        
        total = n*2
        res = 0
        for r in d:
            if sum(d[r])==0:  
                res += 2
            elif sum(d[r])<3:
                res += 1
                
        return total - res
        


class Solution:
    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:
        lookup = collections.defaultdict(list)
        dic = {}
        for row, seat in reservedSeats:
            if row - 1 not in lookup:
                data = [0] * 10
                data[seat-1] = 1
                lookup[row-1] = data
            else:
                lookup[row-1][seat-1] = 1
    
        res = 0           
        for k in lookup:
            data_tup = tuple(lookup[k])
            if data_tup not in dic:
                prev = res
                first = third = False
                if lookup[k][1] or lookup[k][2]  or (lookup[k][1] and lookup[k][2]):
                    if sum(lookup[k][3:7]) == 0 or sum(lookup[k][5:9]) == 0:
                        res += 1
                else:
                    if sum(lookup[k][1:5]) == 0:
                        res += 1
                        first = True
                    if sum(lookup[k][5:9]) == 0:
                        res += 1
                        third = True
                    if not first and not third and sum(lookup[k][3:7]) == 0:
                        res += 1
                dic[data_tup] = res - prev
            else:
                res += dic[data_tup]
            
            
        return res + 2*(n-len(lookup))

class Solution:
    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:
        def isOpen(row, seat):
            for i in range(seat,seat+4):
                if i in grid[row]:
                    return False
            return True
        def isClosed(row,seat):
            return not isOpen(row,seat)
            
            
        grid = {}
        
        for row,seat in reservedSeats:
            if row not in grid: grid[row] = {}
            grid[row][seat] = True
            
        result = n*2
        for i in grid:
            left = isOpen(i,2)
            middle = isOpen(i,4)
            right = isOpen(i,6)
            
            
            if middle:
                if left and right:
                    pass
                else:
                    result -= 1
            else:
                if not left:
                    result -= 1
                if not right:
                    result -= 1
            
            #print(\"\\tleft=%s middle=%s right=%s result=%s\" % (left,middle,right,result))
            
            
        return result

class Solution:
    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:
        BOTH, LEFT, RIGHT, MIDDLE = 0, 1, 2, 3
        required = [
            [2, 3, 4, 5, 6, 7, 8, 9], # BOTH
            [2, 3, 4, 5], # LEFT
            [6, 7, 8, 9], # RIGHT
            [4, 5, 6, 7] # MIDDLE
        ]
        fit = [2, 1, 1, 1]
        res = 0
        d = defaultdict(list)
        for i, j in reservedSeats:
            d[i].append(j)
        res = (n - len(d)) * 2 # 2 for each empty row
        for row in d.values():
            for k, needed in enumerate(required):
                if all(j not in row for j in needed):
                    res += fit[k]
                    break
        return res

class Solution:
    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:
        seats = collections.defaultdict(int)
        for row, col in reservedSeats:
            seats[row] = seats[row] | (1 << (col - 1))

        res = 2 * n
        for reserved in seats.values():
            cnt = 0
            cnt += (reserved & int('0111100000', 2)) == 0
            cnt += (reserved & int('0000011110', 2)) == 0
            cnt += (reserved & int('0001111000', 2)) == 0 and cnt == 0
            res += (cnt - 2)
        return res

from collections import defaultdict

class Solution:
    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:
        d = defaultdict(set)
        for r in reservedSeats:
            d[r[0] - 1].add(r[1] - 1)
        ans = 0
        for i in list(d.keys()):
            j = 0
            while j < 7:
                if j in [1, 3, 5]:
                    if j not in d[i] and j + 1 not in d[i] and j + 2 not in d[i] and j + 3 not in d[i]:
                        ans += 1
                        j += 4
                        continue
                j += 1
        return ans + 2 * (n - len(list(d.keys())))
            


class Solution:
    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:
        seatmap = collections.defaultdict(list)
        
        for row in reservedSeats:
            seatmap[row[0]].append(row[1])
        
        ans = 0
        for row in list(seatmap.keys()):
            row_arrange = [0] * 10
            for each in seatmap[row]:
                row_arrange[each-1] = 1
            print(row_arrange)
            
            if row_arrange[1:5] == [0, 0, 0, 0]:
                ans += 1
            if row_arrange[5:9] == [0, 0, 0, 0]:
                ans += 1
            if row_arrange[3:7] == [0, 0, 0, 0] and row_arrange[1:3] != [0, 0] and row_arrange[7:9] != [0, 0]:
                ans += 1
            print(ans)
        
        return ans + (n - len(seatmap))*2


class Solution:
    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:
        lookup = collections.defaultdict(list)
        dic = {}
        for row, seat in reservedSeats:
            if (row - 1) not in lookup:
                data = [0] * 10
                data[seat-1] = 1
                lookup[row-1] = data
            else:
                data = lookup[row-1]
                data[seat-1] = 1
                lookup[row-1] = data
        res = 0           
        for k in lookup:
            data_tup = tuple(lookup[k])
            if data_tup not in dic:
                prev = res
                first = third = False
                if lookup[k][1] or lookup[k][2]  or (lookup[k][1] and lookup[k][2]):
                    if sum(lookup[k][3:7]) == 0 or sum(lookup[k][5:9]) == 0:
                        res += 1
                else:
                    if sum(lookup[k][1:5]) == 0:
                        res += 1
                        first = True
                    if sum(lookup[k][5:9]) == 0:
                        res += 1
                        third = True
                    if not first and not third and sum(lookup[k][3:7]) == 0:
                        res += 1
                dic[data_tup] = res - prev
            else:
                res += dic[data_tup]
            
            
        return res + 2*(n-len(lookup))

from collections import defaultdict

class Solution:
    def maxNumberOfFamilies(self, n: int, R: List[List[int]]) -> int:
        
        dic = defaultdict(set)
        
        for x, y in R:
            dic[x].add(y)

        res = 2 * ( n - len(dic) )
        
        for v in list(dic.values()):
            if all(j not in v for j in (2,3,4,5)):
                res += 1 + all(j not in v for j in (6,7,8,9))
            else:
                res += (6 not in v and 7 not in v) and (4 not in v and 5 not in v or 8 not in v and 9 not in v)
        
        return res
            
        


class Solution:
    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:
        row_reservations = dict()
        for reserve in reservedSeats:
            row, col = reserve
            if row not in row_reservations:
                row_reservations[row] = set()
            row_reservations[row].add(col)
        
        total = 0
        left = set([2,3,4,5])
        right = set([6,7,8,9])
        center = set([4,5,6,7])
        for row in row_reservations:
            r = row_reservations[row]
            
            if (left & r and right & r and center & r):
                n -= 1
                continue
            
            if not left & r and not right & r:
                total += 2
            else:
                total += 1
            n -= 1
        
        return total + (n * 2)

class Solution:
    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:
        h=defaultdict(list)
        res=0
        for k in reservedSeats:
            h[k[0]].append(k[1])
        for i in list(h.keys()):
            row=h[i]
            if len(row)==1:
                if row[0]==1 or row[0]==10:
                    res+=2
                else:
                    res+=1
            else:
                seats=[0]*10
                for i in row:
                    seats[i-1]=1
                res_copy=res    
                if seats[1:5]==[0,0,0,0]: res+=1
                if seats[5:9]==[0,0,0,0]: res+=1
                if res_copy==res and seats[3:7]==[0,0,0,0]: res+=1
        return res+2*(n-len(list(h.keys())))
        
                    
                
            


class Solution:
    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:
        seatmap = collections.defaultdict(list)
        
        for row in reservedSeats:
            seatmap[row[0]].append(row[1])
        
        ans = 0
        for row in list(seatmap.keys()):
            
            if len(seatmap[row]) == 1:
                if seatmap[row][0] == 1 or seatmap[row][0] == 10:
                    ans += 2
                else:
                    ans += 1
            else:
                row_arrange = [0] * 10
                for each in seatmap[row]:
                    row_arrange[each-1] = 1

                if row_arrange[1:5] == [0, 0, 0, 0]:
                    ans += 1
                if row_arrange[5:9] == [0, 0, 0, 0]:
                    ans += 1
                if row_arrange[3:7] == [0, 0, 0, 0] and row_arrange[1:3] != [0, 0] and row_arrange[7:9] != [0, 0]:
                    ans += 1
        
        return ans + (n - len(seatmap))*2


class Solution:
    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:
        seats = defaultdict(set)
        for i, j in reservedSeats:
            if j in {2, 3, 4, 5}:
                seats[i].add(0)
            if j in {4, 5, 6, 7}:
                seats[i].add(1)
            if j in {6, 7, 8, 9}:
                seats[i].add(2)
        # For n rows, the maximum number of families that can sit together are 2*n.
        result = 2 * n
        for i in seats:
            if len(seats[i]) == 3:
                #  if all three positions in the row was blocked, the total cnt should be reduced by 2
                result -= 2
            else:
                # If less than 3 positions was blocked, the total cnt should -1.
                result -= 1
        return result


class Solution:
    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:
        lookup = collections.defaultdict(list)
        for row, seat in reservedSeats:
            if row - 1 not in lookup:
                data = [0] * 10
                data[seat-1] = 1
                lookup[row-1] = data
            else:
                lookup[row-1][seat-1] = 1
    
        res , dic = 0, {}
        four_person = (0,0,0,0)
        for data in lookup.values():
            data_tup = tuple(data)
            if data_tup not in dic:
                prev = res
                if data_tup[1:5] == four_person:
                    res += 1
                    if data_tup[5:9] == four_person:
                        res += 1
                elif data_tup[3:7] == four_person or data_tup[5:9] == four_person:
                        res += 1 
                dic[data_tup] = res - prev
            else:
                res += dic[data_tup]
                
        return res + 2*(n-len(lookup))

class Solution:
    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:
        ht = {}
        
        for i, j in reservedSeats:
            if not (i-1) in ht:
                ht[i-1] = [0] * 10
            ht[i-1][j-1] = 1
        
        ans = (n-len(ht)) * 2
        
        for i in ht:
            inc = 0
            if ht[i][1:5] == [0, 0, 0, 0]:
                inc += 1
            if ht[i][5:9] == [0, 0, 0, 0]:
                inc += 1
            if inc >= 1:
                ans += inc
                continue
            if ht[i][3:7] == [0, 0, 0, 0]:
                ans += 1
        
        return ans

class Solution:
    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:
        reservedSeats.sort()
        matrix = {}
        for i in range(len(reservedSeats)):
            k = reservedSeats[i][0]
            if k in matrix:
                matrix[k].append(reservedSeats[i][1])
            else:
                matrix[k] = [reservedSeats[i][1]]

        res = 2 * n
        for k, v in matrix.items():
            left_group = mid_group = right_group = True
            if 2 in v or 3 in v:
                left_group = False

            if 4 in v or 5 in v:
                left_group = False
                mid_group = False

            if 6 in v or 7 in v:
                mid_group = False
                right_group = False

            if 8 in v or 9 in v:
                right_group = False

            if left_group or right_group:
                mid_group = False

            res -= 2 - (left_group + mid_group + right_group)

        return res

class Solution:
    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:
        seatmap = collections.defaultdict(list)
        
        for row in reservedSeats:
            seatmap[row[0]].append(row[1])
        
        ans = 0
        for row in list(seatmap.keys()):
            
            # if len(seatmap[row]) == 1:
            #     if seatmap[row][0] == 1 or seatmap[row][0] == 10:
            #         ans += 2
            #     else:
            #         ans += 1
            # else:
            row_arrange = [0] * 10
            for each in seatmap[row]:
                row_arrange[each-1] = 1

            if row_arrange[1:5] == [0, 0, 0, 0]:
                ans += 1
            if row_arrange[5:9] == [0, 0, 0, 0]:
                ans += 1
            if row_arrange[3:7] == [0, 0, 0, 0] and row_arrange[1:3] != [0, 0] and row_arrange[7:9] != [0, 0]:
                ans += 1
        
        return ans + (n - len(seatmap))*2


class Solution:
    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:
        res = 0
        rows = defaultdict(list)
        # store in dict a list of seat numbers for each row:
        for seat in reservedSeats:
            rows[seat[0]].append(seat[1])
     
        for row in list(rows.keys()):
            seat_nums = rows[row]
            
            # if there is only one reserved chair, there are two options:
            if len(seat_nums) == 1:
                res = res+2 if seat_nums[0] in [1, 10] else res+1
    
            else:
                # help list to find reserved seats in current row:
                help_list = [0]*10
                for seat in seat_nums:
                    help_list[seat-1] = 1
                
                res_copy = res
                if help_list[1:5] == [0,0,0,0]: res+=1
                    
                if help_list[5:9] == [0,0,0,0]: res+=1

                if res_copy == res and help_list[3:7] == [0,0,0,0]: res+=1

        # add two to res for each empty row
        return res + 2 * (n-len(list(rows.keys())))


class Solution:
    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:
        lookup = collections.defaultdict(list)
        for row, seat in reservedSeats:
            if row - 1 not in lookup:
                data = [0] * 10
                data[seat-1] = 1
                lookup[row-1] = data
            else:
                lookup[row-1][seat-1] = 1
    
        res , dic = 0, {}
        four_person = [0,0,0,0]
        for data in lookup.values():
            data_tup = tuple(data)
            if data_tup not in dic:
                prev = res
                if data[1:5] == four_person:
                    res += 1
                    if data[5:9] == four_person:
                        res += 1
                elif data[3:7] == four_person or data[5:9] == four_person:
                        res += 1 
                dic[data_tup] = res - prev
            else:
                res += dic[data_tup]
                
        return res + 2*(n-len(lookup))

class Solution:
    def maxNumberOfFamilies(self, n: int, reserved: List[List[int]]) -> int:
        def getGroups(row):
            res = 0
            for group in [left, right]:
                if group.isdisjoint(d[row]): res += 1
            if res >= 1: return res 

            if middle.isdisjoint(d[row]): res += 1 
            return res

        ans = 0
        d = defaultdict(set)
        left, middle, right = set([2,3,4,5]), set([4,5,6,7]), set([6,7,8,9])

        for row, col in reserved: d[row].add(col)
        for row in d: ans += getGroups(row)
        m = len(d)

        return ans+(n-m)*2 

class Solution:
    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:
        reservedSeats.sort()
        count = 2 * (reservedSeats[0][0] - 1)
        row_start = 0
        while row_start < len(reservedSeats):
            row_end = row_start
            indices = []
            while row_end < len(reservedSeats) and reservedSeats[row_end][0] == reservedSeats[row_start][0]:
                indices.append(reservedSeats[row_end][1])
                row_end += 1
            if len(indices) == 1:
                if indices[0] == 1 or indices[0] == 10:
                    count += 1
                count += 1
            elif len(indices) == 2:
                if indices[0] == 1 and indices[1] == 10:
                    count += 2
                elif (all(i not in indices for i in [2, 3, 4, 5]) or
                      all(i not in indices for i in [4, 5, 6, 7]) or
                      all(i not in indices for i in [6, 7, 8, 9])):
                    count += 1
            elif len(indices) <= 6:
                if (all(i not in indices for i in [2, 3, 4, 5]) or
                    all(i not in indices for i in [4, 5, 6, 7]) or
                    all(i not in indices for i in [6, 7, 8, 9])):
                    count += 1
            row_start = row_end
            next_row = reservedSeats[row_start][0] if row_start < len(reservedSeats) else n + 1
            count += 2 * (next_row - reservedSeats[row_end - 1][0] - 1)
        return count