Leetcode 855. Exam Room

Problem Explanation: In the problem, you'll need to create a class "ExamRoom" which will take a parameter called 'n' representing the total number of seats in a room. This class should have two methods one of which will be "seat()", and the other one "leave(p)". The seat() method should return an integer representing a seat number where a student will sit. The algorithm will find the seat that maximizes the distance to the closest student. If there are multiple such seats, the student will sit in the seat with the lowest number. When no one is in the room, then the student sits at seat number 0. On the other hand, the leave(p) method will represent a student leaving the room.

The outline of the solution includes utilizing simple data structures such as 'students' and 'map'. The 'students' list maintains the sorted list of students and the 'map' maintains the seat number (p) to the respective list iterator mapping. We then have the students list, which contains the seats which are already occupied. While the map maps the seat to the student sitting there.

Using this, the seat() method always tries to handle three cases. The first one is when the room is empty, the second one is when there are some students in the room, the last case is when the students list has reached its capacity. When the room is empty, the student just sits at seat number 0. When there are some students in the room, a seat with maximum distances from others is selected. The method maintains a variable 'maxDistToClosest' to keep track of the maximum distance to the closest student. When the students list is full, the student sits at the last seat 'n - 1'. Finally the leave(p) method just removes the seat number 'p' from the students list.

Example Walkthrough: For example, consider the input: ["ExamRoom","seat","seat","seat","seat","leave","seat"], [[10],[],[],[],[],[4],[]]

Here, ExamRoom(10) -> null indicates that there are initially 10 seats and no one has occupied any seats. When seat() is called, it returns 0 because no one is in the room, so the student sits at seat number 0. Next, when seat() is called again, it returns 9 because it maximizes the distance to the closest student (who is at seat number 0). When seat() is called again, it returns 4 because this location maximizes the distance to the closest students (who are at seat number 0 and 9). Next, seat() returns 2 and the similar logic applies here. When leave(4) is called, the student at seat number 4 leaves. Next time when seat() is called, it returns 5, because this location maximizes the distance to the closest students and among such seats with maximum distance, it has the lowest number.

Solution in Python:

1
2python
3class ExamRoom:
4    def __init__(self, N):
5        self.N = N
6        self.students = []
7
8    def seat(self):
9        if not self.students:
10            student = 0
11        else:
12            # 10^9 is big enough to use as a large starting value for d (distance)
13            dist, student = max((self.students[0], 0), max((self.students[i+1] - self.students[i]) // 2, self.students[i]) for i in range(len(self.students) - 1), (self.N - 1 - self.students[-1], self.N - 1))
14        bisect.insort(self.students, student)
15        return student
16
17    def leave(self, p):
18        self.students.remove(p)
19
20# Using the class
21room = ExamRoom(10)
22print(room.seat()) # will print 0
23print(room.seat()) # will print 9
24print(room.seat()) # will print 4
25print(room.seat()) # will print 2
26print(room.leave(4)) # will return None because it's not returning anything
27print(room.seat()) # will print 5

In this Python solution, we use bisect function of the python standard library to maintain the sorted students list by seat order. Though we do not directly optimize the leave function in this Python approach (in terms of time complexity), it still passes the constraints provided in problem statement.

Solution in C++:

1
2c++
3struct Interval {
4    int x, y, dist;
5    Interval(int x, int y): x(x), y(y), dist(y-x-1-max((y-1)/2, (x-1)/2)) {}
6    bool operator < (const Interval& rhs) const {
7        return dist < rhs.dist || dist == rhs.dist && x < rhs.x;
8    }
9};
10struct ExamRoom {
11    int N;
12    set<int> seated;
13    set<Interval> intervals;
14    ExamRoom(int n) {
15        N = n;
16        intervals.insert(Interval{-1, N});
17    }
18    int seat() {
19        int seat;
20        auto it = prev(intervals.end()); // maximize distance or minimize seat
21        if (it->x == -1) {
22            seat = 0;
23        } else if (it->y == N) {
24            seat = N-1;
25        } else {
26            seat = (it->x + it->y) / 2;
27        }
28        seated.insert(seat);
29        intervals.erase({it->x, it->y});
30        intervals.insert({it->x, seat});
31        intervals.insert({seat, it->y});
32        return seat;
33    }
34    void leave(int p) {
35        auto right = *seated.lower_bound(p);
36        auto left = *(prev(seated.lower_bound(p)));
37        seated.erase(p);
38        intervals.erase({left, p});
39        intervals.erase({p, right});
40        intervals.insert({left, right});
41    }
42};

This C++ solution is a bit more optimized. To maximize the distance to the nearest student, we can divide the room into "open" intervals where no students are seated. We always want to sit in the seat with the maximum smallest distance to each side. When a student arrives, they sit in the open interval according to the above rule, and then that open interval is split into two new intervals. Conversely, when they leave, the interval merges into one. As the student may arrive and leave in any order, we will need to insert and delete intervals quickly, so we use a std::set intervals here.

Please note that both the Python and C++ solutions have a time complexity of O(log(n)) as they make use of operations such as insertion, deletion, and retrieval which take logarithmic time in a sorted list/tree.Solution in JavaScript:

1
2javascript
3class ExamRoom {
4  constructor(N) {
5    this.N = N;
6    this.students = [];
7  }
8
9  seat() {
10    if (this.students.length === 0) {
11      this.students.push(0);
12      return 0;
13    } else {
14      let maxDist = this.students[0]; 
15      let seat = 0;
16      for (let i = 1; i < this.students.length; i++) {
17        let dist = Math.floor((this.students[i] - this.students[i-1]) / 2);
18        if (dist > maxDist) {
19          maxDist = dist;
20          seat = this.students[i-1] + dist;
21        }
22      }
23      if (this.N - 1 - this.students[this.students.length - 1] > maxDist) {
24        seat = this.N - 1;
25      }
26      const index = this.students.findIndex((el) => el > seat);
27      index === -1 ? this.students.push(seat) : this.students.splice(index, 0, seat);
28      return seat;
29    }
30  }
31
32  leave(p) {
33    this.students = this.students.filter((el) => el !== p);
34  }
35}
36
37// Using the class
38const room = new ExamRoom(10);
39console.log(room.seat()); // will print 0
40console.log(room.seat()); // will print 9
41console.log(room.seat()); // will print 4
42console.log(room.seat()); // will print 2
43room.leave(4); // It's a void function and won't return anything
44console.log(room.seat()); // will print 5

In this JavaScript solution, we maintain a sorted list of students by directly inserting in place with splice(). When selecting the maximum distance, we also account for the distance from the end of the room with N - 1 - this.students[this.students.length - 1].

Solution in Java:

1
2java
3class ExamRoom {
4    int N;
5    TreeSet<Integer> students;
6
7    public ExamRoom(int N) {
8        this.N = N;
9        this.students = new TreeSet<>();
10    }
11
12    public int seat() {
13        int student = 0;
14        if (this.students.size() > 0) {
15            int dist = this.students.first();
16            Integer prev = null;
17            for (Integer s: students) {
18                if (prev != null) {
19                    int d = (s - prev) / 2;
20                    if (d > dist) {
21                        dist = d;
22                        student = prev + d;
23                    }
24                }
25                prev = s;
26            }
27            if (N - 1 - students.last() > dist) student = N - 1;
28        }
29        students.add(student);
30        return student;
31    }
32
33    public void leave(int p) {
34        students.remove(p);
35    }
36}

Java's TreeSet provides a nice O(log n) solution. The TreeSet maintains the ordered list of students, allowing us to consider each pair of adjacent students as well as the special cases of the first or last seat. Like the JavaScript solution, we simply scan through all available seats and select the one with the maximum distance.