855. Exam Room

MediumDesignOrdered SetHeap (Priority Queue)
Leetcode Link

Problem Description

The problem presents an exam room with a single row of n seats sequentially labeled from 0 to n - 1. The goal is to design a class ExamRoom which can handle two types of requests:

  1. When a student enters the room, they should be assigned to sit in a seat that maximizes the distance between them and the nearest other student already in the room. If more than one seat provides this maximum distance, the student should take the seat with the lowest number.

  2. When a student leaves, we need to indicate that the seat number p they were occupying is now vacant.

In essence, we need to enable efficient ways to:

  • Find the best seat when a student enters.
  • Update the information about occupied seats when a student leaves.

Intuition

The solution involves keeping track of the "gaps" between seated students, which can be thought of as potential places for new students to sit. We use the SortedList data structure to maintain these gaps ordered by the priority in which they should be filled. Each gap is represented by a tuple of two integers, indicating the start and end of the gap.

The priority of a gap is determined first by its distance – the larger the gap, the higher the priority since we want to maximize the distance between students. When gaps are of equal distance, the gap starting with the lower seat number is given higher priority.

Here's how we handle the key operations:

  • Initialization (ExamRoom constructor): We start by adding a single gap (-1, n) which represents the whole empty room.

  • Seating a student (seat method): We select the highest priority gap from the sorted list (which will be at index 0 due to how we've ordered the list). The position to seat the new student (p) is the midpoint of the selected gap. Special cases are handled for the first and last positions. After seating the student, we split the gap into two new gaps and update the list accordingly.

  • Student leaves (leave method): When a student leaves, we remove the two gaps that the student's position (p) created, and create a new single gap signifying the newly empty space. We update the list to reflect this change.

  • Adding and removing gaps (add and delete methods): These helper methods are used to add and remove gaps from the sorted list and to maintain auxiliary dictionaries left and right that help us quickly find the adjacent gaps to a specific seat.

To summarize, the intuition behind the solution is to prioritize seat assignment and track vacant spots using gaps between students, efficiently managed using the SortedList data structure.

Learn more about Heap (Priority Queue) patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

How does quick sort divide the problem into subproblems?

Solution Approach

The solution uses a SortedList from the sortedcontainers module to maintain a sorted set of tuples, where each tuple (l, r) represents a potential 'gap' where a student could sit, with l being the seat number to the left of the gap and r being the seat number to the right of the gap. The key for sorting these gaps is a lambda function lambda x: (-dist(x), x[0]), which sorts primarily by the distance in descending order and secondarily by the left seat number in ascending order.

Let's walk through each part of the implementation to see how the operations are carried out:

  • Initialization (__init__ method): A new ExamRoom instance initializes with a SortedList to track the gaps and two dictionaries, left and right, to track which seats are occupied on the left and right of any seat. The constructor adds the initial gap (-1, n) to represent the whole row as open.

  • Seating (seat method):

    1. It retrieves the gap with the highest priority (the first element in self.ts).
    2. It calculates the position p where the student should sit. If the gap starts at -1, the student sits at 0. If the gap ends at n, the student sits at n - 1. Otherwise, the student sits in the middle of the gap.
    3. It removes the selected gap from self.ts.
    4. It adds two new gaps that result from the student sitting down - one gap to the left and one gap to the right of the new student.

  • Leaving (leave method):

    1. It finds the gaps to the left and right of the seat p that the student will leave from.
    2. It removes these two gaps from self.ts.
    3. It adds a new gap that represents the now-unoccupied space from the left of the left gap to the right of the right gap.

  • Gap Addition and Deletion (add and delete methods): add is used to insert a new gap into the sorted list and update the auxiliary dictionaries. Conversely, delete is used to remove a gap from the sorted list and clean up the dictionaries.

The dist function is an inner function that calculates the distance associated with a gap. A special consideration is that a gap starting at -1 or ending at n (indicating the first or last seat of the row) is handled differently. In these cases, the distance is the actual number of seats minus one since sitting at the edges doesn't require a person to sit equidistantly from two other people.

In summary, the solution uses a sorted list to maintain a dynamic priority queue of potential seating 'gaps', and auxiliary dictionaries to facilitate quick updates when students seat and leave. This approach minimizes the distance between seated students and makes efficient seat assignments as students enter and leave the exam room.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of the following is a good use case for backtracking?

Example Walkthrough

Let's illustrate the solution approach with a simple example. Suppose we have an ExamRoom with 5 seats (n = 5).

Initial Setup

When we initialize the ExamRoom, we add a gap (-1, 5) to represent that all seats from 0 to 4 are available.

First seat Operation

A student enters the room and the seat method is called.

  1. We look at the SortedList and find the top priority gap, which is (-1, 5).
  2. Since -1 indicates the beginning of the room, we place the student at seat 0.
  3. The gap (-1, 5) is removed from the sorted list.
  4. Two new gaps are created: (-1, 0) and (0, 5).

Now the list of gaps is (-1, 0) and (0, 5).

Second seat Operation

Another student enters.

  1. The top priority gap is (0, 5) because it has the widest distance.
  2. The student will sit in the middle of this gap which is at the seat number 2 (since (5 - 0) / 2 = 2.5, and we choose the lower seat number).
  3. The gap (0, 5) is removed from the sorted list.
  4. Two new gaps are created: (0, 2) and (2, 5).

The sorted list of gaps is now (-1, 0), (0, 2), and (2, 5).

Third seat Operation

Yet another student comes in.

  1. The top priority gap is (2, 5) by the same logic, offering a distance of 3.
  2. The student sits at seat 4, as that is the end of the gap (since (5 - 2) / 2 = 1.5and we choose the seat that isend of the gap - 1`).
  3. The gap (2, 5) is removed from the sorted list.
  4. Two new gaps are created: (2, 4) and (4, 5).

The sorted list of gaps now contains (-1, 0), (0, 2), (2, 4), and (4, 5).

Fourth seat Operation

One more student enters.

  1. The top priority gaps are (0, 2) and (2, 4), both with the same distance, so we choose the one with the lower starting seat, which is (0, 2).
  2. The student sits at seat 1, which is the only seat between 0 and 2.
  3. The gap (0, 2) is removed from the sorted list.
  4. Since the student sits between 0 and 2, no new gaps are created from this seating since these are adjacent seats.

The sorted list of gaps is now (-1, 0), (1, 2), (2, 4), and (4, 5).

First leave Operation

A student leaves from seat 2.

  1. The adjacent gaps to 2 are (1, 2) and (2, 4).
  2. The gaps (1, 2) and (2, 4) are removed from the sorted list.
  3. A new gap (1, 4) is created, showing the new empty space from seat 1 to 4.

The sorted list of gaps is now (-1, 0), (1, 4), and (4, 5).

This example shows how the solution efficiently seats students in a way that maximizes distance between them, and updates the available seats when a student leaves. The SortedList helps maintain the order of gaps to always fill the best seat available with each new student while the auxiliary dictionaries facilitate quick updates when students leave.

Solution Implementation

1from sortedcontainers import SortedList
2
3class ExamRoom:
4    def __init__(self, n: int):
5        """Initialize an ExamRoom with n seats."""
6        # Helper function to calculate distance between two seats
7        def get_distance(pair):
8            left, right = pair
9            # If seat is at the beginning or end of the row, distance is the number of empty seats
10            # Otherwise, distance is the midpoint between left and right seats
11            return right - left - 1 if left == -1 or right == n else (right - left) // 2
12
13        self.n = n  # Total number of seats
14        # Initialize sorted list to maintain seats and their distances for efficient access
15        # Ordered by distance first, then by left seat index
16        self.sorted_seats = SortedList(key=lambda x: (-get_distance(x), x[0]))
17        self.left_mapping = {}  # Map from seat to the seat to its left
18        self.right_mapping = {}  # Map from seat to the seat to its right
19        self.add((-1, n))  # Add placeholder for the initial distance from -1 to n
20
21    def seat(self) -> int:
22        """Seat a student in the exam room and return the seat number."""
23        # Find the seat with the maximum distance to its neighbors
24        max_distance_seat = self.sorted_seats[0]
25        # Determine the best seat to sit in
26        if max_distance_seat[0] == -1:  # Sit at the first seat if it's the best option
27            seat_index = 0
28        elif max_distance_seat[1] == self.n:  # Sit at the last seat if it's the best option
29            seat_index = self.n - 1
30        else:  # Otherwise, sit in the middle of the two seats
31            seat_index = (max_distance_seat[0] + max_distance_seat[1]) // 2
32      
33        # Update seat mappings by removing the old pair and adding the new pairs
34        self.delete(max_distance_seat)
35        self.add((max_distance_seat[0], seat_index))
36        self.add((seat_index, max_distance_seat[1]))
37      
38        # Return the chosen seat index
39        return seat_index
40
41    def leave(self, p: int) -> None:
42        """A student leaves the seat at index p."""
43        # Retrieve neighboring seats
44        left_neighbor, right_neighbor = self.left_mapping[p], self.right_mapping[p]
45        # Remove the seats that are no longer relevant since the student has left
46        self.delete((left_neighbor, p))
47        self.delete((p, right_neighbor))
48        # Add the new pair created by the student leaving
49        self.add((left_neighbor, right_neighbor))
50
51    def add(self, pair):
52        """Add a new pair of seats and update their mappings."""
53        # Add the pair to the sorted list and update left and right mappings
54        self.sorted_seats.add(pair)
55        self.left_mapping[pair[1]] = pair[0]
56        self.right_mapping[pair[0]] = pair[1]
57
58    def delete(self, pair):
59        """Remove a pair of seats and update their mappings."""
60        # Remove the pair from the sorted list and delete the mappings
61        self.sorted_seats.remove(pair)
62        self.left_mapping.pop(pair[1], None)
63        self.right_mapping.pop(pair[0], None)
64
1import java.util.TreeSet;
2import java.util.HashMap;
3import java.util.Map;
4
5public class ExamRoom {
6    private TreeSet<int[]> seatSet = new TreeSet<>(
7        (a, b) -> {
8            int distanceA = calculateDistance(a);
9            int distanceB = calculateDistance(b);
10            // Compare by distance, then by starting index if distances are equal
11            return distanceA == distanceB ? a[0] - b[0] : distanceB - distanceA;
12        }
13    );
14    // Maps to track the nearest occupied seat to the left and right of each seat
15    private Map<Integer, Integer> leftNeighbour = new HashMap<>();
16    private Map<Integer, Integer> rightNeighbour = new HashMap<>();
17    private int seatCount;
18
19    public ExamRoom(int n) {
20        this.seatCount = n;
21        // Initialize with a dummy seat segment representing the whole row
22        add(new int[] {-1, seatCount});
23    }
24
25    public int seat() {
26        // Get the seat segment representing the largest distance between seated students
27        int[] segment = seatSet.first();
28        int seatPosition = (segment[0] + segment[1]) / 2;
29        // Handle cases where we need to seat at the start or the end
30        if (segment[0] == -1) {
31            seatPosition = 0;
32        } else if (segment[1] == seatCount) {
33            seatPosition = seatCount - 1;
34        }
35        // Remove the current segment and add new segments reflecting the new student being seated
36        remove(segment);
37        add(new int[] {segment[0], seatPosition});
38        add(new int[] {seatPosition, segment[1]});
39        return seatPosition;
40    }
41
42    public void leave(int p) {
43        // Find the immediate neighbours of the leaving student
44        int leftIndex = leftNeighbour.get(p);
45        int rightIndex = rightNeighbour.get(p);
46        // Remove the segments created by the leaving student
47        remove(new int[] {leftIndex, p});
48        remove(new int[] {p, rightIndex});
49        // Create a new segment reflecting the gap left by the student
50        add(new int[] {leftIndex, rightIndex});
51    }
52
53    private int calculateDistance(int[] segment) {
54        int l = segment[0], r = segment[1];
55        // For seats at the beginning or end, use the whole distance minus one
56        if (l == -1 || r == seatCount) {
57            return r - l - 1;
58        } else {
59            // Else, use the half the distance between l and r
60            return (r - l) / 2;
61        }
62    }
63
64    private void add(int[] segment) {
65        seatSet.add(segment);
66        leftNeighbour.put(segment[1], segment[0]);
67        rightNeighbour.put(segment[0], segment[1]);
68    }
69
70    private void remove(int[] segment) {
71        seatSet.remove(segment);
72        leftNeighbour.remove(segment[1]);
73        rightNeighbour.remove(segment[0]);
74    }
75}
76
1#include <set>
2#include <unordered_map>
3#include <utility>
4
5class ExamRoom {
6public:
7    // Constructor which initializes the room with number of seats
8    explicit ExamRoom(int n) : numSeats(n) {
9        seatSegments.insert({-1, n});
10    }
11
12    // Function that finds the best seat in the room
13    int seat() {
14        // Get the segment from the start of the set
15        auto segment = *seatSegments.begin();
16        int seatPosition;
17        // If segment starts from -1 (beginning of the row), select the first seat
18        if (segment.first == -1) {
19            seatPosition = 0;
20        }
21        // If segment ends at numSeats (end of the row), select the last seat
22        else if (segment.second == numSeats) {
23            seatPosition = numSeats - 1;
24        }
25        // Otherwise select the middle seat in the segment
26        else {
27            seatPosition = (segment.first + segment.second) / 2;
28        }
29
30        // Remove the old segment and add the new segments after seating
31        removeSegment(segment);
32        addSegment({segment.first, seatPosition});
33        addSegment({seatPosition, segment.second});
34
35        return seatPosition;
36    }
37
38    // Function that empties a seat
39    void leave(int p) {
40        // Find adjacent seat segments
41        int prev = leftNeighbor[p];
42        int next = rightNeighbor[p];
43
44        // Remove the obsolete segments
45        removeSegment({prev, p});
46        removeSegment({p, next});
47
48        // Add the new combined segment
49        addSegment({prev, next});
50    }
51
52private:
53    int numSeats; // Total number of seats
54    std::set<std::pair<int, int>, compareSegments> seatSegments; // Set of seat segments
55    std::unordered_map<int, int> leftNeighbor; // Maps a seat to its left neighbor seat
56    std::unordered_map<int, int> rightNeighbor; // Maps a seat to its right neighbor seat
57
58    // Helper function to add a pair of seat indices to the set
59    void addSegment(std::pair<int, int> segment) {
60        seatSegments.insert(segment);
61        leftNeighbor[segment.second] = segment.first;
62        rightNeighbor[segment.first] = segment.second;
63    }
64
65    // Helper function to remove a pair of seat indices from the set
66    void removeSegment(std::pair<int, int> segment) {
67        seatSegments.erase(segment);
68        leftNeighbor.erase(segment.second);
69        rightNeighbor.erase(segment.first);
70    }
71
72    // Comparator for set ordered insertion
73    struct compareSegments {
74        bool operator()(const std::pair<int, int>& a, const std::pair<int, int>& b) const {
75            int distanceA = distance(a), distanceB = distance(b);
76            if (distanceA == distanceB) {
77                return a.first < b.first;
78            }
79            return distanceA > distanceB;
80        }
81
82        // Helper function to compute the distance between two seats
83        static int distance(const std::pair<int, int>& segment) {
84            int left = segment.first, right = segment.second;
85            if (left == -1 || right == N) {
86                return right - left - 1;
87            }
88            return (right - left) / 2;
89        }
90    };
91};
92
93static int N; // This static variable holds the number of seats and is used in the comparator
94
1type Segment = [number, number]; // Represents a segment as a tuple with two elements
2
3// Comparator function definition using type assertion for segment tuples
4const compareSegments = (a: Segment, b: Segment): number => {
5  const distanceA = distance(a);
6  const distanceB = distance(b);
7  if (distanceA === distanceB) {
8    return a[0] - b[0];
9  }
10  return distanceB - distanceA;
11};
12
13let numSeats: number; // Total number of seats
14let seatSegments = new Set<Segment>(compareSegments); // Set of seat segments
15const leftNeighbor: Record<number, number> = {}; // Maps a seat to its left neighbor seat
16const rightNeighbor: Record<number, number> = {}; // Maps a seat to its right neighbor seat
17
18// Helper function to compute the distance between two seats
19const distance = (segment: Segment): number => {
20  const [left, right] = segment;
21  if (left === -1 || right === numSeats) {
22    return right - left - 1;
23  }
24  return (right - left) >> 1; // Using bitwise shift as a substitute for integer division
25};
26
27// Helper function to add a pair of seat indices to the set
28const addSegment = (segment: Segment): void => {
29  seatSegments.add(segment);
30  leftNeighbor[segment[1]] = segment[0];
31  rightNeighbor[segment[0]] = segment[1];
32};
33
34// Helper function to remove a pair of seat indices from the set
35const removeSegment = (segment: Segment): void => {
36  seatSegments.delete(segment);
37  delete leftNeighbor[segment[1]];
38  delete rightNeighbor[segment[0]];
39};
40
41// Function that finds the best seat in the room
42const seat = (): number => {
43  const segment = Array.from(seatSegments).sort(compareSegments)[0]; // Get the first segment after sorting
44  let seatPosition: number;
45  if (segment[0] === -1) {
46    seatPosition = 0;
47  } else if (segment[1] === numSeats) {
48    seatPosition = numSeats - 1;
49  } else {
50    seatPosition = (segment[0] + segment[1]) >> 1; 
51  }
52  removeSegment(segment);
53  addSegment([segment[0], seatPosition]);
54  addSegment([seatPosition, segment[1]]);
55  return seatPosition;
56};
57
58// Function that empties a seat
59const leave = (p: number): void => {
60  const prev = leftNeighbor[p];
61  const next = rightNeighbor[p];
62  removeSegment([prev, p]);
63  removeSegment([p, next]);
64  addSegment([prev, next]);
65};
66
Not Sure What to Study? Take the 2-min Quiz：

Problem: Given a list of tasks and a list of requirements, compute a sequence of tasks that can be performed, such that we complete every task once while satisfying all the requirements.

Which of the following method should we use to solve this problem?

Time and Space Complexity

Time Complexity

  • __init__: The time complexity of initializing the ExamRoom class is O(log n) due to inserting the initial range (-1, n) into the sorted list, which has a time complexity of O(log n) for insertions.

  • seat:

    • The time complexity for fetching the largest interval (first index) is O(1) because the list is already sorted.
    • Insertion of new intervals after seating a student has a time complexity of O(log n) for each insertion, due to the binary search and insertion into the sorted list. Since two insertions take place, this becomes O(log n) overall.

  • leave:

    • Deletion of intervals in the leave operation has a time complexity of O(log n) for each deletion due to binary search within the sorted list. Two deletions take place, therefore, it is O(log n) overall.
    • Insertion of the new interval after leaving has a time complexity of O(log n) due to the same reasons as in the seat operation.

  • add and delete:

    • The add operation includes inserting into the sorted list self.ts, which has a time complexity of O(log n), and updating two dictionaries, which is O(1).
    • The delete operation includes removing from the sorted list self.ts, which has a time complexity of O(log n), and updating two dictionaries, which is also O(1).

Space Complexity

  • The space complexity is O(n) due to the data structures (self.ts, self.left, and self.right) storing information about the intervals. The sorted list and both dictionaries will potentially hold information for all seats, hence it scales with n.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

In a binary min heap, the maximum element can be found in:

Recommended Readings

Heap Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos heap svg Priority Queue and Heap What is the relationship between priority queue and heap Priority Queue is an Abstract Data Type and Heap is the concrete data structure we use to implement a priority queue Priority Queue A priority queue

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫