https://leetcode.com/problems/exam-room/

###### Solution

For each new student, there are 3 cases:

• seat at 0: distance = distance to first seated student
• seat at n-1: distance = distance to last seated student
• seat between 2 continuous other students: distance = (next - prev) / 2

We can maintain seat of student by a ordered set to quickly find the the prev and next student's position.

``````    set<int> students;
int n;
ExamRoom(int N) {
n = N;
}

int seat() {
if (students.size() == 0) {
students.insert(0);
return 0;
}

int pos = 0;
int maxDis = *students.begin();
int prev = -1;
for(auto s: students) {
if (prev == -1) {
prev = s;
continue;
}
if ((s - prev) / 2 > maxDis) {
maxDis = (s-prev) / 2;
pos = prev + (s-prev)/2;
}
prev = s;
}

int last = *(--students.end());
if (n-1-last > maxDis) {
maxDis = n-1-last;
pos = n-1;
}

students.insert(pos);
return pos;
}

void leave(int p) {
students.erase(p);
}
``````

Conclusion: for problem that we need to find next and prev number quickly => use set

Similar technique: https://leetcode.com/problems/k-empty-slots/