Ninja and Cinema Hall

Moderate
0/80
Average time to solve is 30m
profile
Contributed by
1 upvote
Asked in companies
OYOMicrosoft

Problem statement

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.

Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
3 5
2 2
2 4
2 6
3 3
3 5
2 2
1 4
2 1
Sample Output 1:
3
3
Explanation of sample input 1:
In the first test case, 
In Row 1 - Two groups can be seated in seats [ 2,3,4,5 ] and [ 6,7,8,9 ]
In Row 2 - No group can be seated.
In Row 3 - One group can be seated in seats [ 6,7,8,9 ]
So a total of 3 groups can be seated.


Test Case 2:
In Row 1 - One group can be seated in seats [ 6,7,8,9 ]
In Row 2 - Two groups can be seated as [ 2,3,4,5 ] and [6,7,8,9 ]
So a total of 3 groups can be seated.

Sample Input 2:
2
4 4
4 6
1 7
4 3
1 4
2 5
1 3
1 4
2 5
1 8  
2 6
Sample Output 2:
4
0
Hint

Can you think of all the possible ways in a row in which a group of people can be seated?

Approaches (1)
Brute Force

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’.
Time Complexity

O(N + M), where ‘N’ is the number of rows in the cinema hall and ‘M’ is number of reserved seats.

 

Since we have traversed through all the rows and the reserved seats. Therefore the time complexity will be O(N + M).

Space Complexity

O(N + M), where ‘N’ is the number of rows in the cinema hall and ‘M’ is number of reserved seats.
 

We have used an extra 2-D array “reservedSeats”  to store all the rows and reserved seats in all rows. Therefore the space complexity will be O(N + M).

Code Solution
(100% EXP penalty)
Ninja and Cinema Hall
Full screen
Console