LeetCode 855: Exam Room Solution
Master LeetCode problem 855 (Exam Room), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.
855. Exam Room
Problem Explanation
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:
- 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.
- For the first student, insert an interval from -1 to n (both inclusive) with distance n.
- 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.
- Split the interval into two new intervals based on the new student's position and update the distances accordingly.
- When a student leaves at position p, find the interval that contains p, remove it from the priority queue, and merge the adjacent intervals.
- 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.
Solution Code
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;
}
}
}Try It Yourself
Loading code editor...
Related LeetCode Problems
Frequently Asked Questions
How to solve LeetCode 855 (Exam Room)?
This page provides optimized solutions for LeetCode problem 855 (Exam Room) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.
What is the time complexity of LeetCode 855 (Exam Room)?
The time complexity for LeetCode 855 (Exam Room) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.
Can I run code for LeetCode 855 on DevExCode?
Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 855 in Java, C++, or Python.