#1386
Cinema Seat Allocation
expert · 1000 · lc medium +32 · verified · 43.7% accepted · 974 likes · top 25%
Description
A cinema has n rows each with seats numbered 1 to 10. The array reservedSeats lists already-taken seats as [row, seat] pairs. A family of four must occupy four consecutive seats within a single row. Return the maximum number of non-overlapping four-person groups that can be accommodated.
Example 1:
Input: n = 3, reservedSeats = [[1,2],[1,3],[1,8],[2,6],[3,1],[3,10]]
Output: 4
Explanation: The figure above shows the optimal allocation for four groups, where seats mark with blue are already reserved and contiguous seats mark with orange are for one group.
Example 2:
Input: n = 2, reservedSeats = [[2,1],[1,8],[2,6]]
Output: 2
Example 3:
Input: n = 4, reservedSeats = [[4,3],[1,4],[4,6],[1,7]]
Output: 4
Code
1
2
3