Ninja theater
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

Question

Ninja theater

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.

Accepted Answer

Brute Force

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 ‘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 query is of the second type
  - Remove the respective seat number from ‘seatNumbers’.
Return ‘answer’.

Space Complexity: OtherExplanation:

O(M), where ‘M’ denotes the total number of queries given in the problem.

In the worst case, we may have to store the seat numbers for all the ‘M’ queries in ‘seatNumbers’ and ‘answer’. This case occurs when we have queries of only the first type.
Hence, the overall space complexity will be O(M).

Time Complexity: OtherExplanation:

O(M ^ 2), where ‘M’ denotes the total number of queries given in the problem.

For each query of type 1 and 2, iterating over the list ‘seatNumbers’ takes O(M) time.

Hence, the overall time complexity will be O(M) * O(M), which is O(M ^ 2).

Java (SE 1.8)

/*

    Time Complexity  :   O(M ^ 2)

    Space Complexity :   O(M)



	where M denotes the total number of queries given in the problem.

*/



import java.util.ArrayList;



public class Solution {

    public static ArrayList ninjaTheater(int n, ArrayList> queries) {

        ArrayList seatNumbers = new ArrayList<>();

        ArrayList answer = new ArrayList<>();

        ;



        // Run a loop over all queries

        for (int j = 0; j < queries.size(); j++) {



            // If the query is of the first type.

            if (queries.get(j).get(0) == 1) {



                if (seatNumbers.size() == 0) {



                    // If the theater is empty the person will sit at seat number 0.

                    seatNumbers.add(0);

                    answer.add(0);

                } else {



                    int n1 = seatNumbers.size();

                    // To store the maximum distance of any empty seat from the closest person

                    int maxDistance = Math.max(seatNumbers.get(0) - 0, n - 1 - seatNumbers.get(n1 - 1));



                    // Run a loop for i from 0 to size of seatNumbers - 2

                    for (int i = 0; i < seatNumbers.size() - 1; i++) {



                        maxDistance = Math.max(maxDistance, (seatNumbers.get(i + 1) - seatNumbers.get(i)) / 2);



                    }



                    // If maxDistance is the same as the distance of the first person from seat

                    // number 0

                    if (maxDistance == (seatNumbers.get(0))) {



                        // As the person will sit on seat number 0

                        seatNumbers.add(0, 0);

                        answer.add(0);

                    } else {



                        boolean found = false;



                        // Run a loop for i from 0 to size of seatNumbers - 2

                        for (int i = 0; i < seatNumbers.size() - 1; i++) {

                            if ((seatNumbers.get(i + 1) - seatNumbers.get(i)) / 2 == maxDistance) {



                                // As the person will sit on the respective empty seat

                                seatNumbers.add(i + 1, ((seatNumbers.get(i + 1) + seatNumbers.get(i)) / 2));



                                answer.add(seatNumbers.get(i + 1));



                                // As we found the required empty seat number

                                found = true;

                                break;

                            }

                        }

                        if (found == false) {



                            // As the person will sit on seat number N - 1

                            seatNumbers.add(n - 1);

                            answer.add(n - 1);

                        }

                    }

                }

            }



            // If the query is of the second type

            else {



                // Remove the 'queries[j][1]' seat number from seatNumbers



                for (int i = 0; i < seatNumbers.size(); i++) {

                    int x = seatNumbers.get(i);

                    int y = queries.get(j).get(1);

                    if (x == y) {

                        seatNumbers.remove(i);

                        break;

                    }

                }



            }

        }



        return answer;



    }

}

Python (3.5)

'''

    Time Complexity  :   O(M ^ 2)

    Space Complexity :   O(M)



	where ‘M’ denotes the total number of queries given in the problem.

'''



def ninjaTheater(n, queries):



	seatNumbers =[] 

	answer = []



	# Run a loop over all queries

	for j in range(len(queries)):



		# If the query is of the first type.

		if (queries[j][0] == 1):



			if (len(seatNumbers) == 0):



				# If the theater is empty, the person will sit at seat number 0.

				seatNumbers.append(0)

				answer.append(0)

			else :



				# To store the maximum distance of any empty seat from the closest person

				maxDistance = max(seatNumbers[0] - 0, n - 1 - seatNumbers[-1])



				# Run a loop for ‘i’ from 0 to size of ‘seatNumbers’ - 2

				for i in range(len(seatNumbers) - 1):



					maxDistance = max(maxDistance, (seatNumbers[i + 1] - seatNumbers[i]) // 2)



				# If ‘maxDistance’ is the same as the distance of the first person from seat number 0

				if (maxDistance == (seatNumbers[0] - 0)):



					# As the person will sit on seat number 0

					seatNumbers.insert(0, 0)

					answer.append(0)

				else :



					found = False



					# Run a loop for ‘i’ from 0 to size of ‘seatNumbers’ - 2

					currentSize = len(seatNumbers) - 1

					for i in range(currentSize):

						if ((seatNumbers[i + 1] - seatNumbers[i]) // 2 == maxDistance):



							# As the person will sit on the respective empty seat

							seatNumbers.insert(i + 1, (seatNumbers[i + 1] + seatNumbers[i]) // 2)

							answer.append(seatNumbers[i + 1])



							# As we found the required empty seat number

							found = True

							break



					if (found == False):



						# As the person will sit on seat number ‘N’ - 1

						seatNumbers.append(n - 1)

						answer.append(n - 1)

					

		# If the query is of the second type

		else :



			# Remove the 'queries[j][1]' seat number from ‘seatNumbers’

			currentSize = len(seatNumbers)

			toRemove = []

			for i in  range(currentSize):

				if (seatNumbers[i] == queries[j][1]):

					toRemove.append(queries[j][1])



			for e in toRemove:

				seatNumbers.remove(e)

				

	return answer

C++ (g++ 5.4)

/*
    Time Complexity  :   O(M ^ 2)
    Space Complexity :   O(M)

	where ‘M’ denotes the total number of queries given in the problem.
*/

vector ninjaTheater(int n, vector> &queries) {

	vector seatNumbers;
	vector answer;

	// Run a loop over all queries
	for (int j = 0; j < queries.size(); j++) {

		// If the query is of the first type.
		if (queries[j][0] == 1) {

			if (seatNumbers.size() == 0) {

				// If the theater is empty, the person will sit at seat number 0.
				seatNumbers.push_back(0);
				answer.push_back(0);
			}
			else {

				// To store the maximum distance of any empty seat from the closest person
				int maxDistance = max(seatNumbers[0] - 0, n - 1 - seatNumbers.back());

				// Run a loop for ‘i’ from 0 to size of ‘seatNumbers’ - 2
				for (int i = 0; i < seatNumbers.size() - 1; i++) {

					maxDistance = max(maxDistance, (seatNumbers[i + 1] - seatNumbers[i]) / 2);

				}

				// If ‘maxDistance’ is the same as the distance of the first person from seat number 0
				if (maxDistance == (seatNumbers[0] - 0)) {

					// As the person will sit on seat number 0
					seatNumbers.insert(seatNumbers.begin(), 0);
					answer.push_back(0);
				}
				else {

					bool found = false;

					// Run a loop for ‘i’ from 0 to size of ‘seatNumbers’ - 2
					for (int i = 0; i < seatNumbers.size() - 1; i++) {
						if ((seatNumbers[i + 1] - seatNumbers[i]) / 2 == maxDistance) {

							// As the person will sit on the respective empty seat
							seatNumbers.insert(seatNumbers.begin() + i + 1, (seatNumbers[i + 1] + seatNumbers[i]) / 2);
							answer.push_back(seatNumbers[i + 1]);

							// As we found the required empty seat number
							found = true;
							break;
						}
					}
					if (found == false) {

						// As the person will sit on seat number ‘N’ - 1
						seatNumbers.push_back(n - 1);
						answer.push_back(n - 1);
					}
				}
			}
		}

		// If the query is of the second type
		else {

			// Remove the 'queries[j][1]' seat number from ‘seatNumbers’
			for (int i = 0; i < seatNumbers.size(); i++) {
				if (seatNumbers[i] == queries[j][1]) {
					seatNumbers.erase(seatNumbers.begin() + i);
				}
			}
		}
	}

	return answer;
}

Accepted Answer

Using Ordered Set

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.
Return ‘answer’.

Space Complexity: OtherExplanation:

O(M), where ‘M’ denotes the total number of queries given in the problem.

In the worst case, we may have to store the seat numbers for all the ‘M’ queries in hashmaps and ‘answer’. This case occurs when we have queries of only the first type. Also, ‘emptyIntervals’ will take O(M) space to store all the intervals of empty seats.
Hence, the overall space complexity will be O(M).

Time Complexity: OtherExplanation:

O(M * log(M)), where ‘M’ denotes the total number of queries given in the problem.

For each query of type 1 and 2, insertion and deletion of intervals in the ordered set of intervals take O(log(M)) time as the ordered set uses Red-Black tree internally.

Hence, the overall time complexity will be O(M) * O(log(M)), which is O(M * log(M)).

Java (SE 1.8)

/*

    Time Complexity  :   O(M * log(M))

    Space Complexity :   O(M)



    where M denotes the total number of queries given in the problem.

*/



import java.util.ArrayList;

import java.util.Arrays;

import java.util.Comparator;

import java.util.HashMap;

import java.util.NavigableSet;

import java.util.Set;

import java.util.TreeSet;

import java.util.Collections;



class sortbydist implements Comparator> {



    int globalN;



    sortbydist(int n) {

        globalN = n;

    }



    public int compare(ArrayList emptyInterval1, ArrayList emptyInterval2) {

        // We will compute the maximum distance of any empty seat in 'emptyInterval1'

        // from the closest person.

        int maxDistance1;



        if (emptyInterval1.get(0) == 0) {



            // As the person can sit on seat number 0.

            maxDistance1 = emptyInterval1.get(1) - 0;

        } else if (emptyInterval1.get(1) == (globalN - 1)) {



            // As the person can sit on seat number 'N' - 1.

            maxDistance1 = (globalN - 1) - emptyInterval1.get(0);

        } else if (emptyInterval1.get(1) < emptyInterval1.get(0)) {



            // If the interval is empty we will take the distance as -1

            maxDistance1 = -1;

        } else {



            // As the middle seat will be at the maximum distance from the closest person.

            maxDistance1 = (emptyInterval1.get(1) - emptyInterval1.get(0)) / 2;

        }



        // Similarly we will compute the maximum distance of any empty seat in

        // 'emptyInterval2' from the closest person.

        int maxDistance2;



        if (emptyInterval2.get(0) == 0) {



            // As the person can sit on seat number 0.

            maxDistance2 = emptyInterval2.get(1) - 0;

        } else if (emptyInterval2.get(1) == (globalN - 1)) {



            // As the person can sit on seat number 'N' - 1.

            maxDistance2 = (globalN - 1) - emptyInterval2.get(0);

        } else if (emptyInterval2.get(1) < emptyInterval2.get(0)) {



            // If the interval is empty we will take the distance as -1

            maxDistance2 = -1;

        } else {



            // As the middle seat will be at the maximum distance from the closest person.

            maxDistance2 = (emptyInterval2.get(1) - emptyInterval2.get(0)) / 2;

        }



        // If distance of any seat from the closest person in both intervals are

        // different.

        if (maxDistance1 != maxDistance2) {



            // We will sort the intervals in decreasing order of maximum distance.

            return maxDistance2 - maxDistance1;

        } else {



            // We will sort the intervals in increasing order of seat numbers.

            return emptyInterval1.get(0) - emptyInterval2.get(0);

        }



    }



}



public class Solution {

    public static ArrayList ninjaTheater(int n, ArrayList> queries) {



        NavigableSet> emptyIntervals = new TreeSet<>(new sortbydist(n));



        // Since initially [0, 'N' - 1] is an interval of empty seats in the theater.

        emptyIntervals.add(new ArrayList<>(Arrays.asList(0, n - 1)));



        // To store the seat number of the immediate left and right persons from the

        // current position

        HashMap leftPerson = new HashMap<>();

        HashMap rightPerson = new HashMap<>();



        ArrayList answer = new ArrayList<>();



        // Run a loop over all queries.

        for (int j = 0; j < queries.size(); j++) {



            // If the query is of the first type

            if (queries.get(j).get(0) == 1) {



                ArrayList temp = emptyIntervals.first();

                ArrayList currInterval = new ArrayList<>(temp);

                emptyIntervals.remove(temp);



                int currSeat;



                // If Seat number 0 is empty

                if (currInterval.get(0) == 0) {



                    // As it will be at the maximum distance from the closest person.

                    currSeat = 0;

                }



                // Else if Seat number 'N' - 1 is empty

                else if (currInterval.get(1) == (n - 1)) {



                    // As it will be at the maximum distance from the closest person.

                    currSeat = n - 1;

                } else {



                    // As the middle seat will be at the maximum distance from the closest person.

                    currSeat = (currInterval.get(0) + currInterval.get(1)) / 2;

                }



                // We will insert intervals ['currInterval[0]', 'currSeat' - 1] and ['currSeat'

                // + 1, 'currInterval[1]']

                emptyIntervals.add(new ArrayList<>(Arrays.asList(currInterval.get(0), currSeat - 1)));

                emptyIntervals.add(new ArrayList<>(Arrays.asList(currSeat + 1, currInterval.get(1))));



                answer.add(currSeat);



                // Update the values of leftPerson and rightPerson for currInterval[0], currSeat

                // - 1, currSeat + 1, and currInterval[1] accordingly.

                rightPerson.put(currInterval.get(0), currSeat);

                leftPerson.put(currInterval.get(1), currSeat);

                leftPerson.put(currSeat - 1, currInterval.get(0) - 1);

                rightPerson.put(currSeat + 1, currInterval.get(1) + 1);

            }



            // If the query is of the second type

            else {



                int pos = queries.get(j).get(1);



                // As the person is leaving the theater, we will merge the intervals of empty

                // seats to the immediate left and right of this person.

                emptyIntervals.remove(new ArrayList<>(Arrays.asList(leftPerson.get(pos - 1) + 1, pos - 1)));

                emptyIntervals.remove(new ArrayList<>(Arrays.asList(pos + 1, rightPerson.get(pos + 1) - 1)));

                emptyIntervals

                        .add(new ArrayList<>(Arrays.asList(leftPerson.get(pos - 1) + 1, rightPerson.get(pos + 1) - 1)));



                // Update the values of leftPerson and rightPerson for leftPerson[pos - 1]

                // + 1 and rightPerson[pos + 1] - 1 accordingly.

                rightPerson.put(leftPerson.get(pos - 1) + 1, rightPerson.get(pos + 1));

                leftPerson.put(rightPerson.get(pos + 1) - 1, leftPerson.get(pos - 1));

            }

        }



        return answer;



    }



}

Python (3.5)

'''

    Time Complexity  :   O(M * log(M))

    Space Complexity :   O(M)



    where ‘M’ denotes the total number of queries given in the problem.

'''



from heapq import heappop, heappush



globalN = 0

emptyIntervals = []

heapDict = {}



'''

    This function is used 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

'''

def insert(start,end):



       # We will compute the maximum distance of any empty seat in 'emptyInterval1' from the closest person.

        global emptyIntervals



        maxDistance = 0

        if start == 0:

            maxDistance = end - start

        elif end == globalN - 1:

            maxDistance = (globalN - 1) - start

        elif start > end:

            maxDistance = -1

        else:

            maxDistance = (end - start) // 2



        # Push maxDistance, interval and mark this interval valid as true

        currentInterval = [-maxDistance, start, end, True]

        heappush(emptyIntervals,currentInterval)



        # Store in dictionary to use it for marking invalid as it will be deleted from heap

        heapDict[(start, end)] = currentInterval

        

def ninjaTheater(n, queries):



    global globalN

    global emptyIntervals

    global heapDict

    

    heapDictLeft = {}

    heapDictRight = {}

    globalN = n

    emptyIntervals = []



    # Since initially [0, 'N' - 1] is an interval of empty seats in the theater.

    insert(0, n - 1)



    # To store the seat number of the immediate left and right persons from the current position

    leftPerson = {}

    rightPerson = {}



    answer = []



    # Run a loop over all queries.

    for j in range(len(queries)):



        # If the query is of the first type

        if (queries[j][0] == 1):



            while True:



                currInterval = heappop(emptyIntervals)

                

                # We have founded a valid interval

                if currInterval[3] == True:

                    break

                else:

                    if (currInterval[1],currInterval[2]) in heapDict:

                        del heapDict[(currInterval[1],currInterval[2])]

            

            currSeat = -1



            # If Seat number 0 is empty

            if (currInterval[1] == 0) :



                # As it will be at the maximum distance from the closest person.

                currSeat = 0



            # Else if Seat number 'N' - 1 is empty

            elif (currInterval[2] == (n - 1)) :



                # As it will be at the maximum distance from the closest person.

                currSeat = n - 1

            else :



                # As the middle seat will be at the maximum distance from the closest person.

                currSeat = (currInterval[2] + currInterval[1]) // 2



            # We will insert intervals ['currInterval[0]', 'currSeat' - 1] and ['currSeat' + 1, 'currInterval[1]']

            insert(currInterval[1], currSeat - 1)

            insert(currSeat + 1, currInterval[2])



            answer.append(currSeat)



            # Update the values of ‘leftPerson’ and ‘rightPerson’ for ‘currInterval[0]’, ‘currSeat’ - 1, ‘currSeat’ + 1, and ‘currInterval[1]’ accordingly.

            rightPerson[currInterval[1]] = currSeat

            leftPerson[currInterval[2]] = currSeat

            leftPerson[currSeat - 1] = currInterval[1] - 1

            rightPerson[currSeat + 1] = currInterval[2] + 1



        # If the query is of the second type

        else :



            pos = queries[j][1]



            '''

            As the person is leaving the theater, we will merge the intervals of empty seats to the immediate left and right of this person.

            To do this mark 3rd element of heap element as False.

            '''

            # As the person is leaving the theater, we will merge the intervals of empty seats to the immediate left and right of this person.

            

            if (leftPerson[pos - 1] + 1, pos - 1) in heapDict:

                x = heapDict[(leftPerson[pos - 1] + 1, pos - 1)]

                x[3] = False

            if (pos + 1, rightPerson[pos + 1] - 1) in heapDict:

                x = heapDict[(pos + 1, rightPerson[pos + 1] - 1)]

                x[3] = False

            

            insert(leftPerson[pos - 1] + 1, rightPerson[pos + 1] - 1)



            rightPerson[leftPerson[pos - 1] + 1] = rightPerson[pos + 1]

            leftPerson[rightPerson[pos + 1] - 1] = leftPerson[pos - 1]

      

    return answer

C++ (g++ 5.4)

/*
    Time Complexity  :   O(M * log(M))
    Space Complexity :   O(M)

    where ‘M’ denotes the total number of queries given in the problem.
*/

#include 
#include 

int globalN;

/*
    This comparator is used 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
*/
struct comp {
    bool operator() (const vector &emptyInterval1, const vector &emptyInterval2) const {

        // We will compute the maximum distance of any empty seat in 'emptyInterval1' from the closest person.
        int maxDistance1;

        if (emptyInterval1[0] == 0) {

            // As the person can sit on seat number 0.
            maxDistance1 = emptyInterval1[1] - 0;
        }
        else if (emptyInterval1[1] == (globalN - 1)) {

            // As the person can sit on seat number 'N' - 1.
            maxDistance1 = (globalN - 1) - emptyInterval1[0];
        }
        else if (emptyInterval1[1] < emptyInterval1[0]) {

            // If the interval is empty we will take the distance as -1
            maxDistance1 = -1;
        }
        else {

            // As the middle seat will be at the maximum distance from the closest person.
            maxDistance1 = (emptyInterval1[1] - emptyInterval1[0]) / 2;
        }

        // Similarly we will compute the maximum distance of any empty seat in 'emptyInterval2' from the closest person.
        int maxDistance2;

        if (emptyInterval2[0] == 0) {

            // As the person can sit on seat number 0.
            maxDistance2 = emptyInterval2[1] - 0;
        }
        else if (emptyInterval2[1] == (globalN - 1)) {

            // As the person can sit on seat number 'N' - 1.
            maxDistance2 = (globalN - 1) - emptyInterval2[0];
        }
        else if (emptyInterval2[1] < emptyInterval2[0]) {

            // If the interval is empty we will take the distance as -1
            maxDistance2 = -1;
        }
        else {

            // As the middle seat will be at the maximum distance from the closest person.
            maxDistance2 = (emptyInterval2[1] - emptyInterval2[0]) / 2;
        }

        // If distance of any seat from the closest person in both intervals are different.
        if (maxDistance1 != maxDistance2) {

            // We will sort the intervals in decreasing order of maximum distance.
            return maxDistance1 > maxDistance2;
        }
        else {

            // We will sort the intervals in increasing order of seat numbers.
            return emptyInterval1[0] < emptyInterval2[0];
        }
    }
};

vector ninjaTheater(int n, vector> &queries) {

    globalN = n;

    set, comp> emptyIntervals;

    // Since initially [0, 'N' - 1] is an interval of empty seats in the theater.
    emptyIntervals.insert({0, n - 1});

    // To store the seat number of the immediate left and right persons from the current position
    unordered_map leftPerson, rightPerson;

    vector answer;

    // Run a loop over all queries.
    for (int j = 0; j < queries.size(); j++) {

        // If the query is of the first type
        if (queries[j][0] == 1) {


            vector currInterval = *emptyIntervals.begin();
            emptyIntervals.erase(emptyIntervals.begin());

            int  currSeat;

            // If Seat number 0 is empty
            if (currInterval[0] == 0) {

                // As it will be at the maximum distance from the closest person.
                currSeat = 0;
            }

            // Else if Seat number 'N' - 1 is empty
            else if (currInterval[1] == (n - 1)) {

                // As it will be at the maximum distance from the closest person.
                currSeat = n - 1;
            }
            else {

                // As the middle seat will be at the maximum distance from the closest person.
                currSeat = (currInterval[0] + currInterval[1]) / 2;
            }

            // We will insert intervals ['currInterval[0]', 'currSeat' - 1] and ['currSeat' + 1, 'currInterval[1]']
            emptyIntervals.insert({currInterval[0], currSeat - 1});
            emptyIntervals.insert({currSeat + 1, currInterval[1]});

            answer.push_back(currSeat);

            // Update the values of ‘leftPerson’ and ‘rightPerson’ for ‘currInterval[0]’, ‘currSeat’ - 1, ‘currSeat’ + 1, and ‘currInterval[1]’ accordingly.
            rightPerson[currInterval[0]] = currSeat;
            leftPerson[currInterval[1]] = currSeat;
            leftPerson[currSeat - 1] = currInterval[0] - 1;
            rightPerson[currSeat + 1] = currInterval[1] + 1;
        }

        // If the query is of the second type
        else {

            int pos = queries[j][1];

            // As the person is leaving the theater, we will merge the intervals of empty seats to the immediate left and right of this person.
            emptyIntervals.erase({leftPerson[pos - 1] + 1, pos - 1});
            emptyIntervals.erase({pos + 1, rightPerson[pos + 1] - 1});
            emptyIntervals.insert({leftPerson[pos - 1] + 1, rightPerson[pos + 1] - 1});

            // Update the values of ‘leftPerson’ and ‘rightPerson’ for ‘leftPerson[pos - 1]’ + 1  and ‘rightPerson[pos + 1]’  - 1 accordingly.
            rightPerson[leftPerson[pos - 1] + 1] = rightPerson[pos + 1];
            leftPerson[rightPerson[pos + 1] - 1] = leftPerson[pos - 1];
        }
    }

    return answer;
}

Note :

Input Format :

Output Format :

Constraints :

Note :

Algorithm:

Top Sanchhaya Education Software Developer Intern interview questions & answers

Popular interview questions of Software Developer Intern