algoadvance

Leetcode 855. Exam Room

Problem Statement

Leetcode Problem 855: Exam Room

An exam room has N seats in a single row, numbered 0 to N-1.

When a student enters the room, they choose a seat such that the distance to the closest other student is maximized. If there are multiple such seats, they choose the seat with the smallest number. If no students are in the room, then the student sits at seat number 0.

Implement the ExamRoom class:

• ExamRoom(int N) Initializes the object of the exam room with N seats.
• int seat() Finds and returns the seat number of the student who sits down next.
• void leave(int p) Indicates that the student sitting at seat p will leave the room. It is guaranteed that there will be a student at seat p.

Clarifying Questions

1. How should the class handle consecutive calls to the seat and leave methods?
2. When calculating the distance to the nearest student, are seats at the edges of the row treated differently?
3. Will the input N always be greater than 0?

Assuming standard constraints and inputs based on the problem description.

Strategy

Given the problem, we need an efficient way to determine the next seat and to keep track of seats that are occupied. We’ll use the rules for maximum distance to decide which seat a student will take. When a student leaves, we need to update our tracking.

We’ll use a TreeSet to maintain the currently occupied seats as it allows for efficient floor/ceiling operations:

• seat(): To find the seat, we’ll iterate over the already seated positions using the TreeSet to find the largest distance or default to seat 0 if it’s the first student.
• leave(int p): Simply remove the seat p from the TreeSet.

Code

import java.util.TreeSet;

class ExamRoom {
    private int N;
    private TreeSet<Integer> seats;

    public ExamRoom(int N) {
        this.N = N;
        seats = new TreeSet<>();
    }

    public int seat() {
        int student = 0;

        if (!seats.isEmpty()) {
            int maxDist = seats.first();
            Integer prev = null;
            for (int s : seats) {
                if (prev != null) {
                    int dist = (s - prev) / 2;
                    if (dist > maxDist) {
                        maxDist = dist;
                        student = prev + dist;
                    }
                }
                prev = s;
            }

            if (N - 1 - seats.last() > maxDist) {
                student = N - 1;
            }
        }

        seats.add(student);
        return student;
    }

    public void leave(int p) {
        seats.remove(p);
    }
}

Time Complexity

• seat(): O(N) in the worst case because we may need to iterate over all occupied seats to find the optimal seat.
• leave(int p): O(log N) due to the TreeSet removal operation.

Explanation

1. Initialization: We initialize the room with N seats and an empty TreeSet to keep track of occupied seats.
2. Seating Logic:
   • If no seats are occupied, seat the first student at 0.
   • Otherwise, consider the distance from the start, between each pair of seated students, and from the last seated student to the end to find the maximum distance.
3. Leaving Logic: Remove the seat p from the TreeSet, updating the state for future seatings.

This approach ensures efficient seat selection and updates based on standard TreeSet operations.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?