Exam Room

• Constructor ExamRoom(n):

  1. Initialize an ArrayList<Integer> called seats to store the positions of occupied seats.
  2. Store the total number of seats n.

• seat() method:

  1. If seats is empty, add 0 to seats and return 0.
  2. Initialize maxDist = -1 and seat = -1 to track the best option found.
  3. Check the first gap (from seat 0 to the first student): The potential seat is 0. The distance is seats.get(0). If this distance is greater than maxDist, update maxDist to this distance and seat to 0.
  4. Check internal gaps (between adjacent students): Iterate through the seats list from the first to the second-to-last student. For each pair of adjacent students at p1 and p2, calculate the midpoint (p1 + p2) / 2. The distance is (p2 - p1) / 2. If this distance is greater than maxDist, update maxDist and set seat to the midpoint.
  5. Check the last gap (from the last student to seat n-1): The potential seat is n-1. The distance is (n - 1) - seats.get(seats.size() - 1). If this distance is greater than maxDist, update maxDist and set seat to n-1.
  6. After checking all gaps, seat holds the best position. Insert this seat into the seats list while maintaining its sorted order. A simple way is to add it and then call Collections.sort().
  7. Return the chosen seat.

• leave(p) method:

  1. Remove the integer p from the seats list. This requires finding the element and shifting subsequent elements.

The core idea is to maintain a sorted list of occupied seat numbers. When a new student needs to be seated, we can iterate through this list to find the largest empty segment (gap) and place the student in the middle of it.

seat() operation:

When seat() is called, we analyze all possible places a student can sit. These places are determined by the gaps between existing students and the gaps at the ends of the row.

1. If the room is empty: The first student sits at seat 0.
2. If the room has students: We calculate the largest possible distance a new student can have from their nearest neighbor. This can be:
   • At seat 0, with a distance of seats.get(0) from the first student.
   • At seat n-1, with a distance of (n-1) - seats.get(seats.size()-1) from the last student.
   • In the middle of any two adjacent students p1 and p2. The best seat is (p1+p2)/2, with a distance of (p2-p1)/2.

We iterate through all these possibilities, find the one that maximizes the distance, and handle ties by choosing the lower seat number. After finding the best seat, we add it to our list and re-sort the list to prepare for the next call.

leave() operation:

When leave(p) is called, we simply find and remove the seat p from our list.

1import java.util.ArrayList;2import java.util.Collections;3import java.util.List;4 5class ExamRoom {6    private List<Integer> seats;7    private int n;8 9    public ExamRoom(int n) {10        this.n = n;11        this.seats = new ArrayList<>();12    }13    14    public int seat() {15        if (seats.isEmpty()) {16            seats.add(0);17            return 0;18        }19 20        int maxDist = seats.get(0);21        int seat = 0;22 23        for (int i = 0; i < seats.size() - 1; ++i) {24            int p1 = seats.get(i);25            int p2 = seats.get(i + 1);26            int dist = (p2 - p1) / 2;27            if (dist > maxDist) {28                maxDist = dist;29                seat = p1 + dist;30            }31        }32 33        if (n - 1 - seats.get(seats.size() - 1) > maxDist) {34            seat = n - 1;35        }36 37        seats.add(seat);38        Collections.sort(seats);39        return seat;40    }41    42    public void leave(int p) {43        seats.remove(Integer.valueOf(p));44    }45}

• Constructor ExamRoom(n):

  1. Initialize a TreeSet<Integer> called seats.
  2. Store the total number of seats n.

• seat() method:

  1. If seats is empty, add 0 to seats and return 0.
  2. The logic for finding the best seat is identical to the ArrayList approach. We check the gap at the start, the gaps in the middle, and the gap at the end.
  3. Start gap: Distance is seats.first(), seat is 0.
  4. Middle gaps: Iterate through the TreeSet. For each adjacent pair of seats p1 and p2, the distance is (p2 - p1) / 2 and the seat is p1 + (p2 - p1) / 2.
  5. End gap: Distance is n - 1 - seats.last(), seat is n-1.
  6. Keep track of the maximum distance and the corresponding seat with the lowest index.
  7. After finding the best seat, add it to the TreeSet using seats.add(seat).
  8. Return the seat.

• leave(p) method:

  1. Call seats.remove(p) to remove the student from the TreeSet.

By replacing the ArrayList with a TreeSet, we gain efficiency for operations that benefit from a sorted, tree-based structure.

seat() operation:

The algorithm to find the best seat remains the same. We still need to check every gap between adjacent students to find the largest one. A TreeSet allows us to get the first (seats.first()) and last (seats.last()) students in O(log k) time, but iterating through all adjacent pairs still takes O(k) time. However, once the best seat is determined, adding it to the TreeSet is an efficient O(log k) operation, as the tree automatically rebalances itself.

leave() operation:

This is where the TreeSet shines. Removing a student at seat p is a standard tree deletion operation, which takes O(log k) time. This is a major improvement over the O(k) time required for an ArrayList.

While seat() is still linear, the overall performance is better due to the much faster leave() calls.

1import java.util.TreeSet;2 3class ExamRoom {4    private TreeSet<Integer> seats;5    private int n;6 7    public ExamRoom(int n) {8        this.n = n;9        this.seats = new TreeSet<>();10    }11    12    public int seat() {13        if (seats.isEmpty()) {14            seats.add(0);15            return 0;16        }17 18        int maxDist = seats.first();19        int seat = 0;20        Integer prev = null;21 22        for (Integer current : seats) {23            if (prev != null) {24                int dist = (current - prev) / 2;25                if (dist > maxDist) {26                    maxDist = dist;27                    seat = prev + dist;28                }29            }30            prev = current;31        }32 33        if (n - 1 - seats.last() > maxDist) {34            seat = n - 1;35        }36 37        seats.add(seat);38        return seat;39    }40    41    public void leave(int p) {42        seats.remove(p);43    }44}

• Data Structures:

  1. TreeSet<Integer> seats: To store occupied seats and efficiently find neighbors (lower, higher).
  2. PriorityQueue<int[]> pq: A max-heap to store available gaps [start, end] and quickly retrieve the best one.

• Comparator for pq:

  1. The PriorityQueue is ordered by a custom comparator.
  2. For a gap [start, end], calculate its effective distance. This is end - start for edge gaps (where start is 0 or end is n-1) and (end - start) / 2 for internal gaps.
  3. The comparator prioritizes the gap with the largest distance. Ties are broken by the smaller seat index.

• seat() method:

  1. Poll the pq to get the best available gap [start, end].
  2. This gap might be stale (invalidated by a previous leave or seat operation). We must loop, polling from the pq, until we find a valid gap. A gap [s, e] is valid if seats.higher(s) equals e (with special logic for boundaries).
  3. Once a valid gap is found, calculate the new seat p.
  4. Add p to the seats TreeSet.
  5. The old gap [start, end] is now split. Add the two new gaps, [start, p] and [p, end], back into the pq.

• leave(p) method:

  1. Use the seats TreeSet to find the neighbors of p: prev = seats.lower(p) and next = seats.higher(p).
  2. Remove p from seats.
  3. The two gaps adjacent to p, [prev, p] and [p, next], are now obsolete. They are merged into a new, larger gap [prev, next].
  4. Add this new merged gap [prev, next] to the pq. The old, smaller gaps are not explicitly removed (lazy deletion); they will be discarded as stale when polled by the seat() method.

The bottleneck in the previous approach was the linear scan to find the best gap. We can eliminate this scan by using a PriorityQueue to maintain the gaps, ordered by their potential to place a student with the maximum distance.

Data Structures

• TreeSet<Integer> seats: As before, this stores the sorted positions of students. Its key role here is to quickly find the neighbors of a student who is leaving, using lower() and higher() in O(log k) time.
• PriorityQueue<int[]> pq: This max-heap stores all the available gaps, represented as [start_seat, end_seat]. A custom comparator ensures that the gap at the top of the heap is always the one that provides the best possible seat placement (i.e., maximizes the distance to the nearest person, with ties broken by lower seat index).

seat() Operation

Instead of scanning, we simply ask the PriorityQueue for the best gap, which is an O(log k) operation. We take that gap, place the new student p, add p to our TreeSet, and then add the two new, smaller gaps created by the placement ([start, p] and [p, end]) back into the PriorityQueue.

leave() Operation and Lazy Deletion

When a student at p leaves, we use the TreeSet to find their neighbors, prev and next. This tells us that the two gaps [prev, p] and [p, next] are now gone, and a new, larger gap [prev, next] has been created. We add this new gap to the PriorityQueue. The crucial insight is that we don't need to remove the old, now-invalid gaps from the PriorityQueue. This is called lazy deletion. We simply leave them there. When the seat() method polls a gap from the queue, it performs a quick check to see if it's still valid (by checking if the start and end points are still adjacent in the TreeSet). If not, it discards the stale gap and polls the next one. This makes both seat() and leave() operations efficient.

1import java.util.PriorityQueue;2import java.util.TreeSet;3 4class ExamRoom {5    private int n;6    private TreeSet<Integer> seats;7    private PriorityQueue<int[]> pq;8 9    public ExamRoom(int n) {10        this.n = n;11        this.seats = new TreeSet<>();12        // The PQ stores intervals [start, end].13        // The comparator prioritizes the interval with the largest distance.14        // Distance for [x, y] is (y - x) / 2.15        // For edge cases [0, x] or [y, n-1], the distance is x or n-1-y.16        // Tie is broken by the smaller start index.17        this.pq = new PriorityQueue<>((a, b) -> {18            int distA = getDistance(a);19            int distB = getDistance(b);20            if (distA != distB) {21                return distB - distA; // Max-heap22            }23            return a[0] - b[0]; // Smaller start index24        });25        pq.offer(new int[]{-1, n}); // Initial gap for the whole room26    }27 28    public int seat() {29        int seat = 0;30        int[] bestGap = pq.poll();31 32        // Lazy deletion: keep polling until we find a valid gap33        while (seats.contains(bestGap[0]) || seats.contains(bestGap[1]) || 34               (bestGap[0] != -1 && seats.higher(bestGap[0]) != null && seats.higher(bestGap[0]) != bestGap[1]) ||35               (bestGap[1] != n && seats.lower(bestGap[1]) != null && seats.lower(bestGap[1]) != bestGap[0])) {36            if(bestGap[0] != -1 && !seats.contains(bestGap[0])){37                 Integer higher = seats.higher(bestGap[0]);38                 if(higher != null) pq.offer(new int[]{bestGap[0], higher});39            }40            if(bestGap[1] != n && !seats.contains(bestGap[1])){41                 Integer lower = seats.lower(bestGap[1]);42                 if(lower != null) pq.offer(new int[]{lower, bestGap[1]});43            }44            bestGap = pq.poll();45        }46 47        if (bestGap[0] == -1) {48            seat = 0;49        } else if (bestGap[1] == n) {50            seat = n - 1;51        } else {52            seat = bestGap[0] + (bestGap[1] - bestGap[0]) / 2;53        }54 55        seats.add(seat);56        pq.offer(new int[]{bestGap[0], seat});57        pq.offer(new int[]{seat, bestGap[1]});58 59        return seat;60    }61 62    public void leave(int p) {63        Integer prev = seats.lower(p);64        Integer next = seats.higher(p);65        seats.remove(p);66        if (prev == null) prev = -1;67        if (next == null) next = n;68        pq.offer(new int[]{prev, next});69    }70 71    private int getDistance(int[] interval) {72        if (interval[0] == -1) {73            return interval[1];74        }75        if (interval[1] == n) {76            return n - 1 - interval[0];77        }78        return (interval[1] - interval[0]) / 2;79    }80}

Note: The lazy deletion logic in the provided snippet is complex and may need refinement for all edge cases. It serves to illustrate the concept.