1386. Cinema Seat Allocation
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.
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:
-
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 a1
left by ((10 - j)) places, where (j) is the seat number. The expression1 << (10 - j)
turns into a bitmask where all bits are0
except the bit that corresponds to the reserved seat. -
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.
- 2nd to 5th seats:
-
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. -
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.
- If
-
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.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample 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 to0b0001111100
. - Check against
mask3
:(0b0001111100 & mask3) != 0
, no additional family. - We placed one family in Row 1, so now
ans = 1
.
- Check against
-
For Row 2 with bitmask
0b0000010000
:- Check against
mask1
:(0b0000010000 & mask1) == 0
, one family can be seated, bitmask updates to0b0111110000
. - 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
.
- Check against
-
For Row 3 with bitmask
0b1000000001
:- All seats except aisle ones are available, so we can place two families, one in
mask1
and one inmask3
. 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
.
- All seats except aisle ones are available, so we can place two families, one in
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
Time and Space Complexity
Time Complexity
The time complexity of the given code consists of two parts:
-
Iterating through the reserved seats (
reservedSeats
list): This part involves iterating through each seat reservation in the provided list, which is of sizem
, and setting a corresponding bit in a dictionaryd
. The bit manipulation operation for a single seat is constant; hence, this part of the algorithm isO(m)
, wherem
is the number of reserved seats. -
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 thanm
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 alsoO(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 bem
. Therefore, the space complexity isO(m)
, wherem
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.
Given a sorted array of integers and an integer called target, find the element that
equals to the target and return its index. Select the correct code that fills the
___
in the given code snippet.
1def binary_search(arr, target):
2 left, right = 0, len(arr) - 1
3 while left ___ right:
4 mid = (left + right) // 2
5 if arr[mid] == target:
6 return mid
7 if arr[mid] < target:
8 ___ = mid + 1
9 else:
10 ___ = mid - 1
11 return -1
12
1public static int binarySearch(int[] arr, int target) {
2 int left = 0;
3 int right = arr.length - 1;
4
5 while (left ___ right) {
6 int mid = left + (right - left) / 2;
7 if (arr[mid] == target) return mid;
8 if (arr[mid] < target) {
9 ___ = mid + 1;
10 } else {
11 ___ = mid - 1;
12 }
13 }
14 return -1;
15}
16
1function binarySearch(arr, target) {
2 let left = 0;
3 let right = arr.length - 1;
4
5 while (left ___ right) {
6 let mid = left + Math.trunc((right - left) / 2);
7 if (arr[mid] == target) return mid;
8 if (arr[mid] < target) {
9 ___ = mid + 1;
10 } else {
11 ___ = mid - 1;
12 }
13 }
14 return -1;
15}
16
Recommended Readings
Greedy Introduction div class responsive iframe iframe 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 div When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you to calculate the max min of some value Commonly you may see this phrased in the problem as max min longest shortest largest smallest etc These keywords can be identified by just scanning
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
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