LeetCode 855: Exam Room

Explanation

To solve this problem efficiently, we can use a priority queue to keep track of the intervals between students in the exam room. When a student leaves, we can update the priority queue with the new intervals. When a student enters, we can find the seat with the maximum distance to the closest person by dequeuing from the priority queue and splitting the interval based on the new student's position.

Algorithm:

1. Initialize a priority queue to store intervals between students. Each interval is represented by its start position, end position, and distance from the closest person.
2. For the first student, insert an interval from -1 to n (both inclusive) with distance n.
3. When a student enters, dequeue the interval with the largest distance. If it's the first student, seat them at position 0. Otherwise, seat them at the midpoint of the interval.
4. Split the interval into two new intervals based on the new student's position and update the distances accordingly.
5. When a student leaves at position p, find the interval that contains p, remove it from the priority queue, and merge the adjacent intervals.
6. Repeat steps 3 to 5 for subsequent students.

Time Complexity:

• The time complexity of the seat operation is O(log n) due to the priority queue operations.
• The time complexity of the leave operation is O(log n) due to updating the priority queue.
• Overall, the algorithm has a time complexity of O(log n) for both seat and leave operations.

Space Complexity:

• The space complexity is O(n) to store the priority queue of intervals.

import java.util.PriorityQueue;

class ExamRoom {
    private PriorityQueue<Interval> pq;
    private int n;

    public ExamRoom(int n) {
        this.n = n;
        pq = new PriorityQueue<>((a, b) -> {
            if (a.dist == b.dist)
                return a.start - b.start;
            return b.dist - a.dist;
        });
        pq.offer(new Interval(-1, n, n));
    }

    public int seat() {
        int seat;
        Interval interval = pq.poll();
        if (interval.start == -1)
            seat = 0;
        else if (interval.end == n)
            seat = n - 1;
        else
            seat = (interval.start + interval.end) / 2;

        pq.offer(new Interval(interval.start, seat, seat - interval.start));
        pq.offer(new Interval(seat, interval.end, interval.end - seat));
        return seat;
    }

    public void leave(int p) {
        Interval left = null, right = null;
        for (Interval interval : pq) {
            if (interval.start == p)
                right = interval;
            if (interval.end == p)
                left = interval;
            if (left != null && right != null)
                break;
        }
        pq.remove(left);
        pq.remove(right);
        pq.offer(new Interval(left.start, right.end, right.end - left.start));
    }

    class Interval {
        int start, end, dist;

        public Interval(int start, int end, int dist) {
            this.start = start;
            this.end = end;
            this.dist = dist;
        }
    }
}