algoadvance

Leetcode 855. Exam Room

Problem Statement

LeetCode Problem 855: Exam Room

In an exam room with N seats, each seat is consecutively numbered from 0 to N-1. When a student enters the room, they should sit down in a seat such that the distance to the closest person is maximized. If there are multiple seats with the same maximum distance, they sit in the seat with the lowest number. If no one is in the room, the student sits at seat number 0.

Implement the ExamRoom class:

• ExamRoom(int N) Initializes the object with N seats.
• int seat() Returns the seat number where the next student will sit.
• void leave(int p) Indicates that the student in seat p has left the room.

Example:

ExamRoom examRoom = new ExamRoom(10);
cout << examRoom.seat(); // returns 0
cout << examRoom.seat(); // returns 9
cout << examRoom.seat(); // returns 4
cout << examRoom.seat(); // returns 2
examRoom.leave(4);
cout << examRoom.seat(); // returns 5

Constraints:

• 1 <= N <= 10^9
• It is guaranteed that seat and leave will be called at most 10^4 times across all test cases.

Clarifying Questions

1. Q: Can there be multiple leave calls in succession before a seat call?
   • A: Yes, students can leave in any order, and the seat function should handle this correctly.
2. Q: Is the room always empty at the start?
   • A: Yes, the room starts empty with no students seated.

Strategy

Data Structure

We need a data structure to efficiently manage and query the current seat occupancy. A possible choice is a set to store the currently occupied seat numbers since it provides efficient insertion, deletion, and lookup.

Seating Strategy

• When seat() is called:
  1. If no students are in the room, seat the first student at position 0.
  2. Traverse between existing seated students to find the max distance.
     • Calculate the distances for each interval.
     • Check the leftmost seat and the rightmost seat separately.
  3. Choose the smallest seat number in case of ties in distance calculation.

Leaving Strategy

• When leave(int p) is called:
  • Simply remove the seat p from the data structure.

Efficient Management

• Using a set, which supports log(n) operations for inserting and deleting seats.

Code

#include <set>
#include <iostream>
using namespace std;

class ExamRoom {
private:
    set<int> seats;
    int N;

public:
    ExamRoom(int N) : N(N) {}

    int seat() {
        if (seats.empty()) {
            seats.insert(0);
            return 0;
        }
        
        // Find the position to sit.
        int maxDist = *seats.begin(); // Check the first position
        int prev = -1;
        int seat = 0;
        
        for(auto it = seats.begin(); it != seats.end(); it++) {
            if (prev != -1) {
                int dist = (*it - prev) / 2;
                if (dist > maxDist) {
                    maxDist = dist;
                    seat = prev + dist;
                }
            }
            prev = *it;
        }
        
        // Check the last position
        if (N - 1 - *seats.rbegin() > maxDist) {
            seat = N - 1;
        }
        
        seats.insert(seat);
        return seat;
    }

    void leave(int p) {
        seats.erase(p);
    }
};

int main() {
    ExamRoom examRoom(10);
    cout << examRoom.seat() << endl; // returns 0
    cout << examRoom.seat() << endl; // returns 9
    cout << examRoom.seat() << endl; // returns 4
    cout << examRoom.seat() << endl; // returns 2
    examRoom.leave(4);
    cout << examRoom.seat() << endl; // returns 5
    return 0;
}

Time Complexity

• seat():
  • Finding the next seat involves iterating through the seated students, which takes O(n), where n is the number of currently seated students.
  • Inserting into a set is O(log n).
  • Thus, overall complexity is approximately O(n).
• leave(p):
  • Removing from a set is O(log n).

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?