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.
Input: n =3, reservedSeats =[[1,2],[1,3],[1,8],[2,6],[3,1],[3,10]]Output: 4Explanation: 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.
The main idea is to use bitmasking to efficiently represent reserved seats in each row. For each row with reservations, we check which four-seat blocks (left, middle, right) are available. Rows without any reservations can always fit two groups.
classSolution {
publicintmaxNumberOfFamilies(int n, int[][] reservedSeats) {
Map<Integer, Integer> row =new HashMap<>();
for (int[] r : reservedSeats)
row.put(r[0], row.getOrDefault(r[0], 0) | (1 << (r[1]- 1)));
int ans = (n - row.size()) * 2;
for (int mask : row.values()) {
int cnt = 0;
if ((mask & 0b0000011110) == 0) cnt++;
if ((mask & 0b0111100000) == 0) cnt++;
if (cnt == 0 && (mask & 0b0001111000) == 0) cnt++;
ans += cnt;
}
return ans;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
classSolution {
funmaxNumberOfFamilies(n: Int, reservedSeats: Array<IntArray>): Int {
val row = mutableMapOf<Int, Int>()
for (r in reservedSeats)
row[r[0]] = row.getOrDefault(r[0], 0) or (1 shl (r[1] - 1))
var ans = (n - row.size) * 2for (mask in row.values) {
var cnt = 0if (mask and 0b0000011110 ==0) cnt++if (mask and 0b0111100000 ==0) cnt++if (cnt ==0&& mask and 0b0001111000 ==0) cnt++ ans += cnt
}
return ans
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
classSolution:
defmaxNumberOfFamilies(self, n: int, reservedSeats: list[list[int]]) -> int:
row = {}
for r, c in reservedSeats:
row[r] = row.get(r, 0) | (1<< (c -1))
ans = (n - len(row)) *2for mask in row.values():
cnt =0if mask &0b0000011110==0:
cnt +=1if mask &0b0111100000==0:
cnt +=1if cnt ==0and mask &0b0001111000==0:
cnt +=1 ans += cnt
return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
use std::collections::HashMap;
impl Solution {
pubfnmax_number_of_families(n: i32, reserved_seats: Vec<Vec<i32>>) -> i32 {
letmut row = HashMap::new();
for r in reserved_seats {
row.entry(r[0]).and_modify(|e|*e |=1<< (r[1] -1)).or_insert(1<< (r[1] -1));
}
letmut ans = (n - row.len() asi32) *2;
for&mask in row.values() {
letmut cnt =0;
if mask &0b0000011110==0 { cnt +=1; }
if mask &0b0111100000==0 { cnt +=1; }
if cnt ==0&& mask &0b0001111000==0 { cnt +=1; }
ans += cnt;
}
ans
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
classSolution {
maxNumberOfFamilies(n: number, reservedSeats: number[][]):number {
constrow=newMap<number, number>();
for (const [r, c] ofreservedSeats)
row.set(r, (row.get(r) ??0) | (1<< (c-1)));
letans= (n-row.size) *2;
for (constmaskofrow.values()) {
letcnt=0;
if ((mask&0b0000011110) ===0) cnt++;
if ((mask&0b0111100000) ===0) cnt++;
if (cnt===0&& (mask&0b0001111000) ===0) cnt++;
ans+=cnt;
}
returnans;
}
}