# 1386. Cinema Seat Allocation
###### tags: `Leetcode` `Medium` `Bit Manipulation`
Link: https://leetcode.com/problems/cinema-seat-allocation/
## 思路
### 思路一
最简单直接的办法 如果某一行没有座位被占 就可以安排两组
如果有座位被占 则分情况讨论
### 思路二
bit manipulation 运算符参考[这里](https://www.runoob.com/java/java-operators.html)
## Code
### 思路一

class Solution {
    public int maxNumberOfFamilies(int n, int[][] reservedSeats) {
        //4-7 2-5 6-9
        Map<Integer, Set<Integer>> map = new HashMap<>();
        for (int[] reservedSeat: reservedSeats){
            map.putIfAbsent(reservedSeat[0], new HashSet<>());
            map.get(reservedSeat[0]).add(reservedSeat[1]);
        }
        int res = 2*(n-map.size());
        for(int row:map.keySet()){
            Set<Integer> set = map.get(row);
            if(absentInSet(set, 2, 9)) res+=2;
            else if(absentInSet(set, 2, 5)||absentInSet(set, 6, 9)||absentInSet(set, 4, 7)) res+=1;
        }
        return res;
    }
    private boolean absentInSet(Set<Integer> set, int a, int b){
        for(int i = a;i <= b;i++){
            if(set.contains(i)) return false;
        }
        return true;
    }
}

### 思路二

class Solution {
    public int maxNumberOfFamilies(int n, int[][] reservedSeats) {
        Map<Integer, Integer> map = new HashMap<>();
        for(int[] reservedSeat : reservedSeats){
            map.put(reservedSeat[0], map.getOrDefault(reservedSeat[0],0)|(1<<reservedSeat[1]));
        }
        int res = 2*(n-map.size());
        for(int row:map.keySet()){
            int cnt = 0;
            int seats = map.get(row);
            if((seats&0b111100)==0) cnt += 1;
            if((seats&0b1111000000)==0) cnt += 1;
            if((seats&0b11110000)==0 && cnt==0) cnt += 1;
            res += cnt;
        }
        return res;
    }
}