1386. Cinema Seat Allocation
- Array
- Hash Table
- Greedy
- Bit Manipulation
- Counting
TIME
O(m)
SPACE
O(m)
Intuition
n reaches 10^9, but there are at most 10^4 reservations, so the overwhelming majority of rows are completely empty. An empty row always seats exactly 2 groups: blocks 2-5 and 6-9 are disjoint, and no third group can fit alongside them. That gives a baseline of 2 * n, and only the handful of rows containing a reservation need individual attention.
Seats 1 and 10 belong to no block, so a row whose only reservations are seats 1 and/or 10 still behaves like an empty row.
Within a row, the three candidate blocks overlap in a specific way: left (2-5) and right (6-9) are disjoint, while middle (4-7) conflicts with both. So a row seats 2 groups only via left + right; otherwise at most 1.
Approach
- Group the reservations by row (a hash map from row to a 10-bit mask of taken seats).
- Start with
total = 2 * n. - For each row that has reservations, compute how many groups it actually supports:
left= seats 2,3,4,5 all freemid= seats 4,5,6,7 all freeright= seats 6,7,8,9 all free- value =
2ifleft && right, else1if any of the three is free, else0
- Adjust the baseline:
total += value - 2for each such row (rows evaluating to 2 contribute nothing, matching the empty-row assumption). - Return
total.
Complexity
- Time: O(m) where m = number of reservations, independent of
n - Space: O(m), the per-row masks
Edge Cases
- Rows with only seat 1 and/or 10 reserved → still 2 groups (those seats are in no block)
- A single reservation at seat 4, 5, 6, or 7 kills the middle block and one side → 1 group
- Rows with no reservations are never enumerated, which is what keeps this O(m) rather than O(n)
- Max answer is
2 * 10^9 < 2^31 - 1, so it fits inint, but uselongintermediates in Java to be safe
Code
from typing import List
from collections import defaultdict
class Solution:
def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:
"""
1386. Cinema Seat Allocation
Time: O(m)
Space: O(m)
"""
# Bit mask of taken seats per row (bit s-1 set means seat s reserved).
taken = defaultdict(int)
for row, seat in reservedSeats:
taken[row] |= 1 << (seat - 1)
LEFT = 0b0000011110 # seats 2,3,4,5
MIDDLE = 0b0001111000 # seats 4,5,6,7
RIGHT = 0b0111100000 # seats 6,7,8,9
total = 2 * n # every untouched row seats exactly 2 groups
for mask in taken.values():
left_free = (mask & LEFT) == 0
mid_free = (mask & MIDDLE) == 0
right_free = (mask & RIGHT) == 0
if left_free and right_free:
value = 2
elif left_free or mid_free or right_free:
value = 1
else:
value = 0
total += value - 2 # correct the baseline for this row
return totalimport java.util.HashMap;
import java.util.Map;
/**
* 1386. Cinema Seat Allocation
* Time: O(m)
* Space: O(m)
*/
class Solution {
private static final int LEFT = 0b0000011110; // seats 2,3,4,5
private static final int MIDDLE = 0b0001111000; // seats 4,5,6,7
private static final int RIGHT = 0b0111100000; // seats 6,7,8,9
public int maxNumberOfFamilies(int n, int[][] reservedSeats) {
// Bit mask of taken seats per row (bit s-1 set means seat s reserved).
Map<Integer, Integer> taken = new HashMap<>();
for (int[] r : reservedSeats) {
taken.merge(r[0], 1 << (r[1] - 1), (a, b) -> a | b);
}
long total = 2L * n; // every untouched row seats exactly 2 groups
for (int mask : taken.values()) {
boolean leftFree = (mask & LEFT) == 0;
boolean midFree = (mask & MIDDLE) == 0;
boolean rightFree = (mask & RIGHT) == 0;
int value;
if (leftFree && rightFree) {
value = 2;
} else if (leftFree || midFree || rightFree) {
value = 1;
} else {
value = 0;
}
total += value - 2; // correct the baseline for this row
}
return (int) total;
}
}