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/