1386. Cinema Seat Allocation

MediumGreedyBit ManipulationArrayHash Table
Leetcode Link

Problem Description

In the given scenario, a cinema consists of n rows, each with 10 seats. These seats are labelled from 1 to 10. The challenge is to find out the maximum number of four-person families that we can seat in the cinema without having anyone sit in a seat that has already been reserved. The array reservedSeats provides us with the information about seats that have been taken (for example, [3,8] means row 3, seat 8 is reserved).

However, there are specific rules we must follow:

  • A family of four must sit in the same row and side by side.
  • The aisle is something to consider since a family can only be split by the aisle if it separates them two by two (two on one side and the other two on the opposite side of the aisle).

Given this setup, we need to determine how many groups of four can be seated in an optimal arrangement.

Intuition

To solve this problem, we can use bitmasking and a greedy approach. The intuition behind this approach can be broken down into the following insights:

  • First, we recognize that there are only a few configurations of four seats that can fit a family: either starting from seat 2, seat 4, or seat 6. These seats will be respectively represented by the masks 0b0111100000, 0b0001111000, and 0b0000011110 in binary where a 1 denotes an occupied seat.
  • Next, we consider that rows without any reserved seats can obviously fit two families (one on each end avoiding the aisle in the middle).
  • For rows with reserved seats, we use a dictionary to keep track of which seats are occupied using bitmasking. A defaultdict is used to store a bitmask per row where a set bit (1) represents an occupied seat.
  • Then, we iterate through each row with at least one reserved seat and check against our family seat masks to see if there's room for a family. For every match, we increment our answer by one and update the mask to reflect the newly occupied seats to ensure we do not double-count space for another family in the same four-seat configuration.
  • If none of the masks fit, it means that we cannot seat a family of four in that specific row without using the exception (2 people on each side of the aisle).
  • By iterating through all the reserved seats and performing the above checks, we can find the maximum number of four-person family groups that can be seated in the cinema.

Learn more about Greedy patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which algorithm should you use to find a node that is close to the root of the tree?

Solution Approach

The solution approach makes use of a hashmap (in Python, a defaultdict of integer type) and bitwise operations. This is executed through the following steps:

  1. Dictionary Creation: A dictionary d is created to keep track of reserved seats for each row. The key is the row number, and the value is a bitmask where each bit corresponds to a seat in the row, and a set bit (1) means the seat is reserved. The bitmask is built by shifting a 1 left by ((10 - j)) places, where (j) is the seat number. The expression 1 << (10 - j) turns into a bitmask where all bits are 0 except the bit that corresponds to the reserved seat.

  2. Defining Seat Masks: Since there are only certain configurations where a family of four can sit together (with no one sitting in the aisle), three masks are predefined to represent these configurations:

    • 2nd to 5th seats: 0b0111100000
    • 4th to 7th seats: 0b0001111000
    • 6th to 9th seats: 0b0000011110

    These masks represent the seats that form a valid group without any of them being an aisle seat.

  3. Initial Count: The initial count ans is set to twice the number of rows without any reservations, as it's possible to fit two families in an empty row.

  4. Row Iteration and Bitmask Checking: The algorithm iterates over each reserved row (x) in the dictionary. For each row, it will then check against each of the three predefined masks to see if any groups of four seats are available:

    • If (x & mask) == 0, this means the seats corresponding to the current mask are all unreserved, and a family can be placed there.
    • The bitmask of the current row is updated with the mask to mark these seats as occupied (x |= mask) to prevent other families from being placed in the same seats.
    • For each successful check, the answer ans is incremented by one.

  5. Final Answer: After all the reserved rows have been processed and the available spaces for families have been calculated, the algorithm returns the total number of families that can be seated, ans.

By utilizing bitmasks to efficiently check seat availability and update seat reservations, and by keeping track of reserved seats per row in a dictionary, the algorithm is able to calculate the maximum number of four-person families that can be seated in the cinema in a time-efficient manner.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of the following array represent a max heap?

Example Walkthrough

Let's walk through a small example to illustrate the solution approach:

Assume a cinema has 3 rows (n = 3), and we have the following reserved seats: reservedSeats = [[1,2], [1,3], [1,8], [2,6], [3,1], [3,10]].

  • Row 1 has seats 2 and 3 reserved.
  • Row 2 has seat 6 reserved.
  • Row 3 has seats 1 and 10 reserved.

Step 1: Dictionary Creation

We create a dictionary to keep track of the reserved seats with bitmasking:

  • For Row 1: reserved seats are 2 and 3, so the bitmask is 0b0000001100.
  • For Row 2: the reserved seat is 6, so the bitmask is 0b0000010000.
  • For Row 3: reserved seats are 1 and 10, so the bitmask is 0b1000000001.

Step 2: Defining Seat Masks

Three predefined masks:

  • For 2nd to 5th seats: mask1 = 0b0111100000.
  • For 4th to 7th seats: mask2 = 0b0001111000.
  • For 6th to 9th seats: mask3 = 0b0000011110.

Step 3: Initial Count

Initially, there are no rows without reservations, so ans = 0.

Step 4: Row Iteration and Bitmask Checking

  • For Row 1 with bitmask 0b0000001100:

    • Check against mask1: (0b0000001100 & mask1) != 0, no family can be seated.
    • Check against mask2: (0b0000001100 & mask2) == 0, one family can be seated, bitmask updates to 0b0001111100.
    • Check against mask3: (0b0001111100 & mask3) != 0, no additional family.
    • We placed one family in Row 1, so now ans = 1.

  • For Row 2 with bitmask 0b0000010000:

    • Check against mask1: (0b0000010000 & mask1) == 0, one family can be seated, bitmask updates to 0b0111110000.
    • Check against mask2: (0b0111110000 & mask2) != 0, no additional family.
    • Check against mask3: (0b0000010000 & mask3) != 0, no family.
    • We placed one family in Row 2, so now ans = 2.

  • For Row 3 with bitmask 0b1000000001:

    • All seats except aisle ones are available, so we can place two families, one in mask1 and one in mask3. But since we only need non-aisle seats for a group of 4, we can ignore this case for simplicity.
    • The bitmask updates to 0b1111111111, marking all seats as taken.
    • We placed two families in Row 3, so now ans = 4.

Step 5: Final Answer

After checking all the reserved rows, we conclude that we can seat ans = 4 families of four in this cinema.

Therefore, in our small example of a 3-row cinema with the given reserved seats, we can optimally fit 4 four-person families.

Solution Implementation

1from collections import defaultdict
2
3class Solution:
4    def maxNumberOfFamilies(self, n: int, reserved_seats: list[list[int]]) -> int:
5        # Create a dictionary to keep track of reserved seats by row.
6        reservations_dict = defaultdict(int)
7      
8        # Populate the reservations_dict with the bitwise representation of the reserved seats.
9        for row, seat in reserved_seats:
10            reservations_dict[row] |= 1 << (10 - seat)
11      
12        # Define masks for the three possible ways a family can sit.
13        # These are bit masks that check sets of 4 seats that are together.
14        family_masks = (0b0111100000, 0b0000011110, 0b0001111000)
15      
16        # Pre-calculate the number of families that can sit without any reservation conflicts.
17        # If a row has no reservations, two families can sit there.
18        answer = (n - len(reservations_dict)) * 2
19      
20        # Check each row with reservations to see how many more families can sit.
21        for reserved_row in reservations_dict.values():
22            for mask in family_masks:
23                # If the family can sit in the checked pattern (mask) without conflicting with reserved seats...
24                if (reserved_row & mask) == 0:
25                    # Mark the seats as taken to avoid double counting.
26                    reserved_row |= mask
27                    # One more family can sit in this row.
28                    answer += 1
29                  
30        # Return the total number of families that can sit together.
31        return answer
32
1class Solution {
2    public int maxNumberOfFamilies(int n, int[][] reservedSeats) {
3        // Define a map to keep track of the reserved seats in each row
4        Map<Integer, Integer> reservedMap = new HashMap<>();
5      
6        // Iterate over the list of reserved seats and update the map
7        // The key is the row number, and the value is a bit mask representing reserved seats
8        for (int[] seat : reservedSeats) {
9            int row = seat[0], seatNum = seat[1];
10            // Set the corresponding bit for the reserved seat
11            reservedMap.merge(row, 1 << (10 - seatNum), (oldValue, value) -> oldValue | value);
12        }
13      
14        // Define the masks that represent the available blocks of 4 seats
15        int[] masks = {
16            0b0111100000, // left block: seats 2-5
17            0b0000011110, // right block: seats 6-9
18            0b0001111000  // middle block: seats 4-7
19        };
20      
21        // Start with the maximum number of families that can be seated without any reservations
22        int ans = (n - reservedMap.size()) * 2;
23      
24        // Iterate over the rows with reservations and find available spots
25        for (int reserved : reservedMap.values()) {
26            for (int mask : masks) {
27                // If all seats represented by a mask are not reserved, increment ans
28                if ((reserved & mask) == 0) {
29                    reserved |= mask; // Update the reserved seats
30                    ++ans;
31                    break; // Once a family is seated, no need to check other masks for this row
32                }
33            }
34        }
35        return ans; // Return the maximum number of families that can be seated
36    }
37}
38
1#include <unordered_map>
2#include <vector>
3
4class Solution {
5public:
6    int maxNumberOfFamilies(int numRows, std::vector<std::vector<int>>& reservedSeats) {
7        // Create a map to hold the occupied seats for each row
8        std::unordered_map<int, int> occupiedSeats;
9
10        // Process the reserved seats and mark them in the occupiedSeats map
11        for (const auto& seat : reservedSeats) {
12            int row = seat[0], col = seat[1];
13            // Create a bitmask and mark the seat as occupied
14            occupiedSeats[row] |= 1 << (10 - col); // Shift bits to the column position
15        }
16
17        // Family seating patterns that can occupy four consecutive seats
18        // Pattern 1: Seats 2, 3, 4, 5 (between aisle seats)
19        // Pattern 2: Seats 6, 7, 8, 9 (between aisle seats)
20        // Pattern 3: Seats 4, 5, 6, 7 (middle seats)
21        int seatingPatterns[3] = {0b0111100000, 0b0000011110, 0b0001111000};
22
23        // Every row not in occupiedSeats can fit 2 families
24        int maxFamilies = (numRows - occupiedSeats.size()) * 2;
25
26        // Go through the occupiedSeats to find the number of families that can fit
27        for (auto& [row, occupied] : occupiedSeats) {
28            for (int& pattern : seatingPatterns) {
29                // Check if the pattern fits in the row
30                if ((occupied & pattern) == 0) {
31                    // If yes, update the occupied bitmask and increase count
32                    occupied |= pattern;
33                    ++maxFamilies;
34                    break; // Only one pattern can fit if another family has already occupied some seats
35                }
36            }
37        }
38
39        return maxFamilies;
40    }
41};
42
1function maxNumberOfFamilies(n: number, reservedSeats: number[][]): number {
2    // Map for storing the reserved seats information per row.
3    const reservedMap: Map<number, number> = new Map();
4
5    // Populating the reservedMap. A bit-mask is created for each row.
6    for (const [row, seat] of reservedSeats) {
7        reservedMap.set(row, (reservedMap.get(row) ?? 0) | (1 << (10 - seat)));
8    }
9
10    // Calculate the maximum number of families that can sit in unreserved rows.
11    let maxFamilies = (n - reservedMap.size) * 2;
12
13    // Define bit-masks for valid family seating positions.
14    const familySeatMasks = [0b0111100000, 0b0000011110, 0b0001111000];
15
16    // Iterate over reserved rows to check if there's a seating configuration
17    // available for a family.
18    for (const [_, reservedSeatsBitmask] of reservedMap) {
19        for (const mask of familySeatMasks) {
20            // If a valid family seating position is empty.
21            if ((reservedSeatsBitmask & mask) === 0) {
22                // Mark the position as occupied to prevent double counting.
23                reservedSeatsBitmask |= mask;
24                // Increment the number of families as we found a spot.
25                maxFamilies++;
26            }
27        }
28    }
29
30    return maxFamilies;
31}
32
Not Sure What to Study? Take the 2-min Quiz：

Which data structure is used to implement recursion?

Time and Space Complexity

Time Complexity

The time complexity of the given code consists of two parts:

  1. Iterating through the reserved seats (reservedSeats list): This part involves iterating through each seat reservation in the provided list, which is of size m, and setting a corresponding bit in a dictionary d. The bit manipulation operation for a single seat is constant; hence, this part of the algorithm is O(m), where m is the number of reserved seats.

  2. Processing the dictionary (d) to count the number of families that can be accommodated: Here, we iterate through each row that has at least one reserved seat (not more than m such rows) and check against three different masks to find a suitable spot for a family of 4. This also involves constant time operations for each row. Therefore, the complexity for this part is also O(m).

Combining the two, the overall time complexity of the algorithm is O(m).

Space Complexity

For space complexity, we mainly consider the dictionary d that is used to store rows with reserved seats:

  • Dictionary (d) to store the reserved seats: The space used by this dictionary depends on how many different rows have reserved seats, which in the worst-case scenario can be m. Therefore, the space complexity is O(m), where m is the number of reserved rows.

Overall, the space complexity of the code is O(m).

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

The three-steps of Depth First Search are:

  1. Identify states;
  2. Draw the state-space tree;
  3. DFS on the state-space tree.

Recommended Readings

Greedy Introduction

Greedy Introduction iframe width 560 height 315 src https www youtube com embed WTslqPbj7I title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫