Solve LeetCode's Cinema Seat Allocation: a 4-person family needs four consecutive seats in a 10-seat row. Only three possible blocks exist (2-5, 4-7, 6-9), so each empty row fits two families max. Track which blocks are blocked by reserved seats, then subtract from two families per row. Time and space complexity are both O(R) for R reserved seats.
Chapters
So, this is a problem of cinema seat allocation problem, but before we dive into that, we have to understand some constraints in the problem. So, problem says that a 4-person group must be assigned to 4 seats in the same row, and in one row there can only be 10 seats, 1 to 10, and the seating arrangement for the group can be one of the following: seats 2, 3, 4, 5, 4, 5, 6, 7, or 6, 7, 8, 9. So which means we have to ignore seat 1 and 10 based on the constraint. And so notice that empty row can fit a maximum of 2 families based on these constraints, one on the left and one on the right. So for example, a group can sit from 2, 3, 4, 5, or 6, 7, 8, 9. Right. So So we'll start by assuming that every row can hold 2 families, family equals 2 times n. We can look at the solution itself. See, we have taken first the constraint left, middle, and right blocks: 2, 3, 4, 5; 4, 5, 6, 7; 6, 7, 8, 9. And then we have created a map And then in the map, we are— each row points to a set of blocked seating groups. So we represent the left, middle, and right groups using 0, 1, and 2. For every reserved seat, we can check which group contains that seat and mark those groups as blocked. For example, reserved seat 4 blocks both the left and middle groups because seat 4 belongs to both. Finally, we process only the rows Containing reservation. So we have taken families equals to 2 into n because we— that is also given in the problem statement that there cannot be more than 2 families in a row based on the sitting constraint. So if all the groups are blocked, that row can hold— cannot hold any family. That's why we are reducing 2. And if 1 or 2 groups are blocked, then the row can still hold 1 family, but then we are subtracting 1 because now only 1 family can adjust in that row. And if there is, if the row, if there is no value for that row, then we are not subtracting anything because we have already reserved the seat for that. So the key idea is that the set does not store reserved seats, it stores which family seating arrangements are no longer possible. The time complexity is O of the number of reserved seats and space complexity is also, also O of the reserved seats.
