Approach 1: Maintain Sorted Positions
ExamRoom.students, a sorted
TreeSet in Java) of positions the students are currently seated in.
ExamRoom.leave(p) operation is clear - we will just
TreeSet.remove) the student from
Let's focus on the
ExamRoom.seat() : int operation. For each pair of adjacent students
j, the maximum distance to the closest student is
d = (j - i) / 2, achieved in the left-most seat
i + d. Otherwise, we could also sit in the left-most seat, or the right-most seat.
Finally, we should handle the case when there are no students separately.
For more details, please review the comments made in the implementations.
Time Complexity: Each
seatoperation is , (where is the number of students sitting), as we iterate through every student. Each
leaveoperation is ( in Java).
Space Complexity: , the space used to store the positions of each student sitting.
Analysis written by: @awice.