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.

Source: leetcode | Difficulty: MEDIUM
Tags: Bit manipulation

Data structures

Greedy algorithms

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 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) = (480, 30)
		mdl_mask = 120
		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:
		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:
		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:
				seat_n = res[row][0]
				if seat_n in [1, 10]:
					fams += 2
				else:
					fams += 1
			else:
				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:
		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}
		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:

	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 = [1 for j in range(10)]
			for j in lookup[i]:
				available[j] = 0
			for (start, end) in [(1, 5), (5, 9)]:
				if sum(available[start:end]) == 4:
					res += 1
					used = True
			if not used and sum(available[3:7]) == 4:
				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
				elif 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:
		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])
		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
			elif 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
				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()))


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:
					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:
		(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 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:
		reservedSeats.sort(key=lambda s: s[0])
		(res, prev_row) = (0, 1)
		taken_slots = collections.defaultdict(lambda : [False, False, False, False])
		for (row, col) in reservedSeats:
			if prev_row != row:
				res += 2 * (row - prev_row - 1)
				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
		res += 2 * (n - prev_row)
		res += self.countAvailableSeats(prev_row, taken_slots)
		return res


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):
					reserved.add((row, col))
					reserved.add((row, col + 1))
					reserved.add((row, col + 2))
					reserved.add((row, col + 3))
					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
		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
			elif 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:
		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


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 = collections.defaultdict(list)
		for (r, c) in reservedSeats:
			lst[r].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


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:
		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
			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)
		for seat in reservedSeats:
			rows[seat[0]].append(seat[1])
		print(rows)
		for row in list(rows.keys()):
			seat_nums = rows[row]
			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
		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:

	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))


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:
			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:

		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
		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], [2, 3, 4, 5], [6, 7, 8, 9], [4, 5, 6, 7]]
		fit = [2, 1, 1, 1]
		res = 0
		d = defaultdict(list)
		for (i, j) in reservedSeats:
			d[i].append(j)
		res = (n - len(d)) * 2
		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


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:
		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, 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