

A cinema&nbsp;has n&nbsp;rows of seats, numbered from 1 to n&nbsp;and there are ten&nbsp;seats in each row, labelled from 1&nbsp;to 10&nbsp;as shown in the figure above.

Given the array reservedSeats containing the numbers of seats already reserved, for example, reservedSeats[i] = [3,8]&nbsp;means the seat located in row 3 and labelled with 8&nbsp;is already reserved.

Return the maximum number of four-person groups&nbsp;you can assign on the cinema&nbsp;seats. A four-person group&nbsp;occupies four&nbsp;adjacent seats in one single row. Seats across an aisle (such as [3,3]&nbsp;and [3,4]) are not considered to be adjacent, but there is an exceptional case&nbsp;on which an aisle split&nbsp;a four-person group, in that case, the aisle split&nbsp;a four-person group in the middle,&nbsp;which means to have two people on each side.

&nbsp;
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


&nbsp;
Constraints:


	1 &lt;= n &lt;= 10^9
	1 &lt;=&nbsp;reservedSeats.length &lt;= min(10*n, 10^4)
	reservedSeats[i].length == 2
	1&nbsp;&lt;=&nbsp;reservedSeats[i][0] &lt;= n
	1 &lt;=&nbsp;reservedSeats[i][1] &lt;= 10
	All reservedSeats[i] are distinct.


class Solution(object):
    def maxNumberOfFamilies(self, n, reservedSeats):
        """
        :type n: int
        :type reservedSeats: List[List[int]]
        :rtype: int
        """
        d = defaultdict(set)
        for row,seat in reservedSeats:
            d[row].add(seat)
        
        def row(i):
            a1 = not set((2,3,4,5)).intersection(d[i])
            a2 = not set((6,7,8,9)).intersection(d[i])
            if  a1 and a2:
                return 2
            if  a1 or a2:
                return 1
            return 1 if not set((4,5,6,7)).intersection(d[i]) else 0
        
        return sum((row(i) for i in d.keys())) + (n-len(d)) * 2
class Solution {
    public int maxNumberOfFamilies(int n, int[][] reservedSeats) {
        Map<Integer, int[]> seats = new HashMap<>();
        int availableSlots = 2 * n; // max available slots since each empty row could fit at max 2 slots

        for (int[] seat: reservedSeats) {
            int row = seat[0];
            int col = seat[1];
            int[] slots = seats.getOrDefault(row, new int[3]);

            if (col >= 2 && col <= 5) { // left slot
                slots[0] = 1;
            }
            if (col >= 4 && col <= 7) { // middle slot
                slots[1] = 1;
            }
            if (col >= 6 && col <= 9) { // right slot
                slots[2] = 1;
            }

            seats.put(seat[0], slots);
        }

        for (int[] slots: seats.values()) {
            int taken = slots[0] + slots[2];

            if (taken == 2) { // both slots at either ends are taken
                if (slots[1] == 0) { // check if middle slot not taken
                    availableSlots--; // reduce availableslots by 1 since middle slot is available
                } else {
                    availableSlots -= 2; // entire row not available - reduce by 2
                }
            } else if (taken == 1) { // one of the slots at either ends are taken
                availableSlots--; // reduce by 1 since either side of the slots not available
            } else {
                continue; // entire row is available - no need to reduce the available slots
            }
        }

        return availableSlots;
    }
}
class Solution {
public:
    int maxNumberOfFamilies(int n, vector<vector<int>>& reservedSeats) {
        unordered_map<int, vector<int>> o;
        
        for (auto r : reservedSeats) {
            
            o[r[0]].push_back(r[1]);
        }
        
        int ans = 2 * (n - o.size()); // seats with no occupancy directly adding 2
        
		// if we iterate from 1 to n (10 ^ 9) we cross time limit
        for (auto p : o) {
            
            // get reserved seats
            vector<int> seats = p.second;
            
            
            int occupied_mask = 0;
            
            // representing occupied seats as bits
            for (int s : seats) {
                if (s > 1 && s < 10) {
                    occupied_mask += (int)pow(2, 10 - s);
                }
            }
            
            // checking 3 seating configurations
            int masks[3] = {480, 120, 30};
            
            int row_ans = 0;
            bool res1 = (masks[0] & occupied_mask) == 0;
            bool res2 = (masks[1] & occupied_mask) == 0;
            bool res3 = (masks[2] & occupied_mask) == 0;
           
			// if all 3 configurations are empty, 2 families
			// if either one of them are empty, 1 family
            if (res1 && res2 && res3) row_ans += 2;
            else if (res1 || res2 || res3) row_ans += 1;
            
            
            ans += row_ans;
            
        }
        
        return ans;
    }
};
/**
 * @param {number} n
 * @param {number[][]} reservedSeats
 * @return {number}
 */
var maxNumberOfFamilies = function(n, reservedSeats) {
    let a,b,c,reservedMap={},ans=n*2,takenB={};
    for(let i=0;i<reservedSeats.length;i++){
        let resverd = reservedSeats[i];
        let row = resverd[0];
        if(reservedMap[row]===undefined){
            reservedMap[row]={}
        }
        if(2<=resverd[1] && resverd[1]<=3 && reservedMap[row]['a']===undefined){//a is blocked now
            ans--;
            reservedMap[row]['a']=true;
            if(reservedMap[row]['c']===true && reservedMap[row]['b']===undefined){
                takenB[resverd[0]]=true;
                ans++;//add for b
            }
        }else if(8<=resverd[1] && resverd[1]<=9 && reservedMap[row]['c']===undefined){//c is blocked now
            ans--;
            reservedMap[row]['c']=true;
            if(reservedMap[row]['a']===true && reservedMap[row]['b']===undefined){
                takenB[resverd[0]]=true;
                ans++;//add for b
            }
        }else if(4<=resverd[1] && resverd[1]<=5){//b is blocked now
            if(reservedMap[row]['a']===undefined){
                ans--;
                reservedMap[row]['a']=true;
            }
            if(takenB[resverd[0]]===true){
                ans--;//substract for b
                takenB[resverd[0]]=false;
            }
            reservedMap[row]['b']=true;
        }else if(6<=resverd[1] && resverd[1]<=7){//b is blocked now
            if(reservedMap[row]['c']===undefined){
                ans--;
                reservedMap[row]['c']=true;
            }
            if(takenB[resverd[0]]===true){
                ans--;//substract for b
                takenB[resverd[0]]=false;
            }
            reservedMap[row]['b']=true;
        }
    }
    return ans;
};
Cinema Seat Allocation