Last Updated: 3 Apr, 2021
Ninja theater
Hard
Asked in companies
You have been appointed as the technical lead in the very famous ninja theater. Due to the recent pandemic, all the people inside the theater must follow social distancing. There are ‘N’ seats in a single row in the ninja theater, numbered from 0 to ‘N’ - 1 inclusive. As a technical lead, your task is to find a seating arrangement for ninja theater such that when a person enters the theater, he/she must sit in the seat that maximizes the distance from the closest person.
Note :
1) If the theater is empty, i.e., if no one is in the theater, they sit in the first seat(seat number 0).
2) If there are multiple seats that maximize the distance from the closest person, they sit in the seat with the lowest number.
Input Format :
The first line of input contains an integer 'T' representing the number of test cases.
The first line of each test case contains a single integer, ‘N’, where ‘N’ denotes the number of seats in a single row in ninja theater.
The second line of each test case contains a single integer, ‘M’, where ‘M’ denotes the number of queries. Here each query can be of two types.
The next ‘M’ lines contain two space-separated integers, ‘type’ and ‘seatNum’, where ‘type’ denotes the query type. For queries of the first type, ‘seatNum’ is -1, whereas, for the second type, it denotes the seat number of the person that leaves the theater.
Note: For every query of the first type, it is guaranteed that at least one seat is empty, and for the query of the second type, it is guaranteed that ‘seatNum’ has a person sitting.
Output Format :
For each test case, for each query of the first type, print ‘K’ space-separated integers denoting the seat numbers that a person should sit to maximize the distance from the closest person. Here ‘K’ denotes the total number of queries of the first type in the current test case.
The output of each test case will be printed in a separate line.
Constraints :
1 <= T <= 5
1 <= N <= 10 ^ 9
1 <= M <= 100
1 <= type <= 2
0 <= seatNum <= ‘N’ - 1
Time Limit : 1 sec
Where ‘T’ is the number of test cases, ‘N’ denotes the number of seats in a single row in ninja theater, ‘M’ denotes the number of queries, type’ denotes the query type, and ‘seatNum’ denotes the seat number of the person that leaves the theater.
Note :
You do not need to print anything, it has already been taken care of. Just implement the given function.
Approaches
The idea here is to maintain a sorted list of seat numbers of the persons sitting in the theater. For every query of type 2, we can directly remove the seat number from our list. For every query of type 1, we will iterate over the list and find the lowest seat number, which is empty and has a maximum distance from the closest person in the theater and place the new person accordingly.
Algorithm:
- Declare a list of integers, say ‘seatNumbers’, to store the seat number of persons sitting in the theater in sorted order.
- Declare an array of integers, say ‘answer’, to store the seat numbers that a person should sit to maximize the distance from the closest person
- Run a loop over all queries.
- If the query is of the first type.
- If the size of ‘seatNumbers’ is 0.
- Insert 0 into ‘seatNumbers’, as the person will sit on seat number 0.
- Insert 0 into ‘answer’.
- Else
- Declare an integer, say ‘maxDistance’, to store the maximum distance of any empty seat from the closest person and initialize it with a maximum of (distance of the first person from seat number 0, distance of the last person from seat number ‘N’ - 1).
- Run a loop for ‘i’ from 0 to size of ‘seatNumbers’ - 2.
- Update ‘maxDistance’ as the maximum of itself and (seatNumbers[i+1] - seatNumbers[i]) / 2.
- If ‘maxDistance’ is the same as the distance of the first person from seat number 0.
- Insert 0 into ‘seatNumbers’, as the person will sit on seat number 0.
- Insert 0 into ‘answer’.
- Else
- Declare a boolean, say ‘found’, and initialize it with false.
- Run a loop for ‘i’ from 0 to size of ‘seatNumbers’ - 2.
- If (seatNumbers[i+1] - seatNumbers[i]) / 2 is same as ’maxDistance’
- Insert (seatNumbers[i+1] + seatNumbers[i]) / 2 into ‘seatNumbers’, as the person will sit on the respective empty seat.
- Insert seatNumbers[i+1] into ‘answer’
- Mark ‘found’ and true and break the loop as we found the required empty seat number.
- If (seatNumbers[i+1] - seatNumbers[i]) / 2 is same as ’maxDistance’
- If ‘found’ is false.
- Insert ‘N’ - 1 into ‘seatNumbers’, as the person will sit on seat number ‘N’ - 1.
- Insert ‘N’ - 1 into ‘answer’.
- If the size of ‘seatNumbers’ is 0.
- If the query is of the second type
- Remove the respective seat number from ‘seatNumbers’.
- If the query is of the first type.
- Return ‘answer’.
The idea here is to consider an interval of empty seats. Initially, when no one is in the theater, the interval of empty seats will be [0, ‘N’ - 1]. For every query of type 1, we will find an interval of empty seats with the lowest seat number and with the maximum distance from the closest person. We will place the person in this interval in such a way that it maximizes the distance from the closest person. Now, for every query of type 2, as the person is leaving the theater, we will merge the intervals of empty seats to the immediate left and right of this person.
Algorithm:
- Declare an ordered set of arrays of size 2, say ‘emptyIntervals’, to store the intervals of empty seats in decreasing order of the maximum distance of any empty seat from the closest person. If there are multiple such empty intervals, intervals are sorted in increasing order of seat numbers. Initialize it with [0, ‘N’ - 1].
- Declare two hashmaps, say ‘leftPerson’ and ‘rightPerson’, to store the seat number of the immediate left and right persons from the current position.
- Declare an array of integers, say ‘answer’, to store the seat numbers that the persons should sit to maximize the distance from their respective closest persons.
- Run a loop over all queries.
- If the query is of the first type.
- Declare an array of size 2, say ‘currInterval’, and initialize it with the first element of ‘emptyIntervals’.
- Remove the first element of ‘emptyIntervals’.
- Declare an integer, say ‘currSeat’, to store the seat number of the empty seat in ‘currInterval’, which maximizes the distance from the closest person.
- If ‘currInterval[0]’ equals 0
- Assign ‘currSeat’ as 0.
- Else if ‘currInterval[1]’ equals ‘N’ - 1
- Assign ‘currSeat’ as ‘N’ - 1
- Else
- Assign ‘currSeat’ as (currInterval[1] + currInterval[0]) / 2.
- Insert the intervals [currInterval[0], currSeat - 1] and [currSeat + 1, currInterval[1]] into ‘emptyIntervals’.
- Insert ‘currSeat’ in ‘answer’, as this is our required seat number.
- Update the values of ‘leftPerson’ and ‘rightPerson’ for ‘currInterval[0]’, ‘currSeat’ - 1, ‘currSeat’ + 1, and ‘currInterval[1]’ accordingly.
- If the query is of the second type
- Assume ‘pos’ is the seat number of the current person.
- Remove the intervals [leftPerson[pos - 1] + 1, pos - 1] and [pos + 1, rightPerson[pos + 1] - 1] from ‘emptyIntervals’.
- Insert the interval [leftPerson[pos - 1] + 1, rightPerson[pos + 1] - 1] into ‘emptyIntervals’.
- Update the values of ‘leftPerson’ and ‘rightPerson’ for ‘leftPerson[pos - 1]’ + 1 and ‘rightPerson[pos + 1]’ - 1 accordingly.
- If the query is of the first type.
- Return ‘answer’.