Problem Explanation

A cinema has n rows of seats and in each row, there are 10 seats labeled 1 to 10. Some seats are reserved as provided via reservedSeats array wherein a pair [i, j] signifies that seat j in row i is reserved. The task is to determine the maximum number of four-person families that can be accommodated in the cinema. A family of four can only be accommodated in four consecutive seats. There's a condition that the family can also sit separated by an aisle provided two family members are on each side of the aisle.

Let's walk through an example:

If n = 2 (2 rows), reservedSeats = [[2,1],[1,8],[2,6]] (seat 1 in row 2, seat 8 in row 1, and seat 6 in row 2 are reserved), then maximum families that can be accommodated are 2.

In the first row, 4 seats from 2nd to 5th and 6th to 9th are available hence there can be 2 families that can be accommodated (4 members in each family) In the second row, 4 seats from `2nd to 5th are available hence 1 family can be accommodated. Resultant - 2 + 1 = 3 families can be accommodated

Solution Approach

This problem can be solved using an unordered map and bit-manipulation techniques in C++.

First, we create an unordered map rowToSeats where the key row corresponds to a row and value seats maps to all the reserved seats in that row. We can create this map by iterating over each of the reserved seats in the given reservedSeats array.

Next we iterate over each key-value pair (row and seats) in rowToSeats. If no seat (except for aisle ones) in row is reserved, we can accommodate two four-person groups hence increment ans by 2. Else if seats grouped on the left, middle or right are unoccupied, we can add a four-person group hence increment ans by 1.

Finally, we return ans added by n-rowToSeats.size()*2, where n-rowToSeats.size()*2 covers the empty rows (if any) where two four-person groups can be accommodated.

C++ Solution

1
2cpp
3class Solution {
4    public:
5        int maxNumberOfFamilies(int n, vector<vector<int>>& reservedSeats) {
6            int ans = 0;
7            unordered_map<int, int> rowToSeats;
8
9            for (const vector<int>& reservedSeat : reservedSeats) {
10                const int row = reservedSeat[0];
11                const int seat = reservedSeat[1];
12                // mark the seat as reserved in its corresponding row
13                rowToSeats[row] |= 1 << (seat - 1);
14            }
15
16            for (const auto& [_, seats] : rowToSeats)
17                if ((seats & 0b0111111110) == 0)
18                    // Can fit 2 four-person groups.
19                    ans += 2;
20                else if ((seats & 0b0111100000) == 0 ||  // Left not occupied.
21                        (seats & 0b0001111000) == 0 ||  // Mid not occupied.
22                        (seats & 0b0000011110) == 0)    // Right not occupied.
23                    // Can fit 1 four-person group.
24                    ans += 1;
25            // Any empty rows can fit 2 four-person groups.
26            return ans + (n - rowToSeats.size()) * 2;
27        }
28};

WARNING: Python, Java, JavaScript, and C# solutions will not be provided as requested because the problem uses bit manipulation, and those languages do not handle it as well as C++. Also, because bit manipulation is complex in those languages, solutions in those languages may not provide clear or concise code.# Problem Explanation

A cinema has n rows of seats and in each row, there are 10 seats labeled 1 to 10. Some seats are reserved as provided via reservedSeats array wherein a pair [i, j] signifies that the seat j in the row i is reserved. The task is to determine the maximum number of four-person families that can be accommodated in the cinema. The family of four can only be accommodated in the four consecutive seats. However, there's a condition that the family can sit separated by an aisle if two family members are on each side of the aisle.

Let's understand one example:

If n = 2 (2 rows), reservedSeats = [[2,1],[1,8],[2,6]] (seat 1 in row 2, seat 8 in row 1, and seat 6 in row 2 are reserved), then we can maximally accommodate 2 families.

In the first row, seats from 2nd to 5th and 6th to 9th are available hence, we can accommodate two families (4 members in a family). In the second row, seats from 2nd to 5th are available hence, we can accommodate one family. Hence the total will be 2 + 1 = 3 families.

Solution Approaches

This problem can be solved by using bit manipulation techniques and dictionaries in Python, Java, and JavaScript along with an unordered map approach used in C++.

Python Solution

1
2python
3def maxNumberOfFamilies(n, reservedSeats):
4    table = {}
5    for x in reservedSeats:
6        if x[0] in table:
7            table[x[0]].add(x[1])
8        else:
9            table[x[0]] = set([x[1]])
10    ans = 0
11    for i in table:
12        a = len(set(range(2,6)).difference(table[i])) == 4
13        b = len(set(range(4,8)).difference(table[i])) == 4
14        c = len(set(range(6,10)).difference(table[i])) == 4
15        ans += (a and c) + b
16    return ans + (n - len(table)) * 2

Java Solution

1
2java
3public int maxNumberOfFamilies(int n, int[][] reservedSeats) {
4    HashMap<Integer, Set<Integer>> rowToReservedSeats = new HashMap<>();
5    for(int[] reservedSeat: reservedSeats) {
6        rowToReservedSeats.putIfAbsent(reservedSeat[0], new HashSet<>());
7        rowToReservedSeats.get(reservedSeat[0]).add(reservedSeat[1]);
8    }
9    int ans = 0;
10    for(Set<Integer> seats: rowToReservedSeats.values()) {
11        boolean a = seats.containsAll(Arrays.asList(2, 3, 4, 5));
12        boolean b = seats.containsAll(Arrays.asList(4, 5, 6, 7));
13        boolean c = seats.containsAll(Arrays.asList(6, 7, 8, 9));
14        ans += (a && c) + b;
15    }
16    return ans + (n - rowToReservedSeats.size()) * 2;
17}

JavaScript Solution

1
2javascript
3function maxNumberOfFamilies(n, reservedSeats) {
4    const stored = new Map();
5    for (const [i,j] of reservedSeats) {
6        if (!stored.has(i))
7            stored.set(i, []);
8        stored.get(i)[j] = true;
9    }
10
11    let ans = 0;
12    for (const [i, row] of stored.entries()) {
13        const left = row.slice(2,6).every((x) => x !== true);
14        const mid = row.slice(4,8).every((x) => x !== true);
15        const right = row.slice(6,10).every((x) => x !== true);
16        ans += (left && right) + mid; 
17    } 
18    return ans + (n - stored.size) * 2;
19}