Last Updated: 14 Apr, 2021
Ninja and Cinema Hall
Moderate
Asked in companies
Ninja just started his new job at a cinema hall where there are ‘N’ number of rows with 10 seats in each row. Each seat is labeled with a number from 1 to 10. You are given an M x 2 2-D array/list “NON_VACANT”, where NON_VACANT[i][j] denotes that the seat located in a row ‘i’ and labeled ‘j’ is not vacant.
Ninja can assign seats in only groups of four people such that they all sit adjacent to each other in one single row. Help Ninja in finding the maximum number of the four people groups he can assign seats to.
Note:
Seats 3,4 and 7,8 are considered as not adjacent to each other.
There is an exceptional case in which seats 3,4 and seat 7,8 are considered to be adjacent and Ninja can split the group from the middle and assign seats to two people on each side.
Ninja can assign seats to a group of four people in the below depicted three manners.
Input Format
The first line contains an integer ‘T’ which denotes the number of test cases or queries to be run. Then the test cases are as follows.
The first line of each test case contains two space-separated integers ‘N’, and ‘M’, denoting the number of rows in the cinema hall and the number of reserved seats.
The next ‘M’ line contains two space-separated integers denoting the row number and seat number of reserved seats.
Output Format:
For each test case, return a single integer denoting the maximum number of the four-people groups that can be seated adjacently.
Note:
You don’t need to print anything; It has already been taken care of.
Constraints:
1 <= T <= 10
1 <= N <= 10^5
0 <= M <= 10*N
1 <= NON_VACANT[i][0] <= N
1 <= NON_VACANT[i][1] <= 10
Time limit: 1 sec
Approaches
At first, it can be seen that the number of four-people groups that can be seated in a particular row is independent of all the other rows. So, if we know how to find the number of groups in a particular row, then similarly we can find it for all the other rows and our final answer will be the total number of groups in all rows.
Now, let's see how we can find the number of groups for a particular row:
We can simplify our solution from seat 2 to seat 9.
We will divide the seats into four sections:
Section1 - seat 2, 3
Section2 - seat 4, 5
Section3 - seat 6, 7
Section4 - seat 8, 9
- Now if all four sections are vacant, then 2 groups can be seated.
- Otherwise, if section2 and section3 are vacant, then 1 group can be seated
- Otherwise, if section1 and section2 are vacant, then 1 group can be seated.
- Otherwise, If section3 and section4 are vacant, then 1 group can be seated.
- If none of the above conditions is true, then no group can be seated.
So we will check the vacant sections in each row and calculate the total number of four-group people that can be seated.
Algorithm:
- Initialize a 2-D array “RESERVED_SEATS” of size ‘N+1’ where RESERVED_SEATS[ i ] denotes an array of integers containing the seat numbers reserved in the ‘i'th’ row.
- Initialize a variable “RES” to store the result.
- Run a loop i: 0 to M-1
- Push all the non-vacant seats in ‘RESERVED_SEATS’ corresponding to the row number.
- Iterate through “RESERVED_SEATS” vector using a variable ‘i’ (initial value as 1)
- Initialize four variables ‘SECTION_ONE’, ‘SECTION_TWO’, ‘SECTION_THREE’, ‘SECTION_FOUR’ with initial values 1 which denotes that all the four sections are vacant initially. Updating these variables to 0 denotes that these sections are now not empty.
- Now iterate through every ‘SEAT’ reserved in the current row.
- If the seat is labelled either 2 OR 3, Update ‘SECTION_ONE’ as 0
- If the seat is labelled either 4 OR 5, Update ‘SECTION_TWO’ as 0
- If the seat is labelled either 6 OR 7, Update ‘SECTION_THREE’ as 0
- If the seat is labelled either 8 OR 9, Update ‘SECTION_FOUR’ as 0
- If all the four variables are 1 that means all the four sections are vacant, increment ‘RES’ by 2.
- Otherwise, if ‘SECTION_ONE’ and ‘SECTION_TWO’ are 1, increment ‘RES’ by 1.
- Otherwise if ‘SECTION_TWO’ and ‘SECTION_THREE’ are 1, increment ‘RES’ by 1.
- Otherwise if ‘SECTION_THREE’ and ‘SECTION_FOUR’ are 1, increment ‘RES’ by 1.
- Return ‘RES’.