Leetcode 855: Exam Room
You are tasked with simulating an exam room where students will choose seats based on a strategy that maximizes their distance from the closest person already seated. If multiple seats have the same distance, the student will choose the seat with the smallest index. Additionally, students can leave the room, freeing up their seats.
Problem
Approach
Steps
Complexity
Input: The input consists of an integer n, which represents the number of seats in the exam room. The object should allow for two operations: seating a student and having a student leave a seat.
Example: Input:
["ExamRoom", "seat", "seat", "seat", "seat", "leave", "seat"]
[[10], [], [], [], [], [4], []]
Constraints:
• 1 <= n <= 10^9
• At most 10^4 calls will be made to the 'seat' and 'leave' operations.
Output: For each 'seat' operation, return the seat index where the student will sit. For the 'leave' operation, there is no return value.
Example: Output:
[null, 0, 9, 4, 2, null, 5]
Constraints:
Goal: To implement the seating strategy such that students sit at the seat that maximizes the distance from the nearest student. If there are multiple options, choose the smallest seat index.
Steps:
• Step 1: Implement a data structure to track the positions of students already seated.
• Step 2: For each 'seat' operation, calculate the maximum distance to the nearest student for each empty seat and choose the seat that maximizes this distance.
• Step 3: For each 'leave' operation, remove the seat from the list of occupied seats.
Goal: Ensure efficient handling of the seating strategy given that the number of seats n can be very large.
Steps:
• Seats are indexed from 0 to n-1, and each student occupies a unique seat at a time.
Assumptions:
• There will always be at least one seat available when a student arrives.
• Input: Input:
["ExamRoom", "seat", "seat", "seat", "seat", "leave", "seat"]
[[10], [], [], [], [], [4], []]
• Explanation: Initially, no student is seated. The first student sits at seat 0. The next student sits at the farthest available seat, seat 9. The next one sits at seat 4 (the middle of the remaining seats). The next student sits at seat 2. When the student at seat 4 leaves, the next student sits at seat 5 (the next best available seat).
Approach: To efficiently manage seating and leaving operations, we maintain a list of occupied seats and calculate the optimal seat choice for each 'seat' operation.
Observations:
• The problem requires balancing between finding the optimal seat and managing the students' movements.
• A list of occupied seats is essential to calculate the seat with the greatest distance to the nearest student.
Steps:
• Step 1: Track occupied seats using a list or similar structure.
• Step 2: For each new student, calculate the distance from each occupied seat and choose the seat that maximizes this distance.
• Step 3: Update the list of occupied seats when a student leaves a seat.
Empty Inputs:
• N/A: The problem guarantees there is always at least one seat and one student.
Large Inputs:
• Efficient handling of operations is necessary when n is large, up to 10^9.
Special Values:
• If there is only one student and one seat, the student always sits at seat 0.
Constraints:
• There is a guarantee that no student will leave a seat that is unoccupied.
vector<int> L;
public:
ExamRoom(int n) {
N = n;
}
int seat() {
if(L.size() == 0) {
L.push_back(0);
return 0;
}
int d = max(L[0], N - 1 - L[L.size() - 1]);
for(int i = 0; i < L.size() - 1; i++) d = max(d, (L[i + 1] - L[i]) /2);
if(L[0] == d) {
L.insert(L.begin(), 0);
return L[0];
}
for(int i = 0; i < L.size() - 1; i++) {
if((L[i + 1] - L[i])/2 == d) {
L.insert(L.begin() + i + 1, (L[i] + L[i +1])/2);
return L[i + 1];
}
}
L.push_back(N - 1);
return N - 1;
}
void leave(int p) {
for(int i = 0; i < L.size(); i++) if(L[i] == p) L.erase(L.begin() + i);
}
};
/**
* Your ExamRoom object will be instantiated and called as such:
* ExamRoom* obj = new ExamRoom(n);
* int param_1 = obj->seat();
* obj->leave(p);
1 : Data Structures
vector<int> L;
Declares a vector `L` to store the positions of people in the room.
2 : Access Modifiers
public:
Indicates that the following methods are publicly accessible.
3 : Constructor
ExamRoom(int n) {
Constructor of the `ExamRoom` class, initializing the room with a given size `n`.
4 : Initialization
N = n;
Initializes the variable `N` with the given size of the room `n`.
5 : Method Definition
int seat() {
Defines the `seat()` method, which assigns a seat to a person based on available space.
6 : Conditionals
if(L.size() == 0) {
Checks if the room is empty. If it is, it assigns the first seat at position 0.
7 : Action
L.push_back(0);
Inserts the first person at position 0.
8 : Return
return 0;
Returns the position of the newly seated person (0).
9 : Distance Calculation
int d = max(L[0], N - 1 - L[L.size() - 1]);
Calculates the maximum distance between the first and last seats.
10 : Loop
for(int i = 0; i < L.size() - 1; i++) d = max(d, (L[i + 1] - L[i]) / 2);
Calculates the maximum possible distance between two people in the room.
11 : Conditional Check
if(L[0] == d) {
Checks if the maximum distance is between the first seat and the available space.
12 : Action
L.insert(L.begin(), 0);
Inserts a new person at the first seat.
13 : Return
return L[0];
Returns the position of the newly seated person (0).
14 : Loop
for(int i = 0; i < L.size() - 1; i++) {
Starts a loop to find the best seat based on the maximum distance.
15 : Conditional Check
if((L[i + 1] - L[i]) / 2 == d) {
Checks if the gap between two adjacent seats is half of the maximum distance.
16 : Action
L.insert(L.begin() + i + 1, (L[i] + L[i +1]) / 2);
Seats the person at the optimal position between two others.
17 : Return
return L[i + 1];
Returns the position where the person was seated.
18 : Action
L.push_back(N - 1);
Inserts a new person at the last seat.
19 : Return
return N - 1;
Returns the position of the newly seated person (last seat).
20 : Method Definition
void leave(int p) {
Defines the `leave(int p)` method, which removes a person from the room at position `p`.
21 : Loop
for(int i = 0; i < L.size(); i++) if(L[i] == p) L.erase(L.begin() + i);
Finds the person at position `p` and removes them from the list.
Best Case: O(1) for a single seat when no one is in the room.
Average Case: O(n) for finding the best seat when a student is seated.
Worst Case: O(n) per 'seat' operation in the worst case, where the seating strategy requires checking multiple seats.
Description:
Best Case: O(1) when no students are in the room.
Worst Case: O(n) for storing the list of occupied seats.
Description:
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus