There is an exam room with n seats in a single row labeled from 0 to n - 1.

When a student enters the room, they must sit in the seat that maximizes the distance to the closest person. If there are multiple such seats, they sit in the seat with the lowest number. If no one is in the room, then the student sits at seat number 0.

Design a class that simulates the mentioned exam room.

Implement the ExamRoom class:


	ExamRoom(int n) Initializes the object of the exam room with the number of the seats n.
	int seat() Returns the label of the seat at which the next student will set.
	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 sitting at seat p.


&nbsp;
Example 1:

Input
["ExamRoom", "seat", "seat", "seat", "seat", "leave", "seat"]
[[10], [], [], [], [], [4], []]
Output
[null, 0, 9, 4, 2, null, 5]

Explanation
ExamRoom examRoom = new ExamRoom(10);
examRoom.seat(); // return 0, no one is in the room, then the student sits at seat number 0.
examRoom.seat(); // return 9, the student sits at the last seat number 9.
examRoom.seat(); // return 4, the student sits at the last seat number 4.
examRoom.seat(); // return 2, the student sits at the last seat number 2.
examRoom.leave(4);
examRoom.seat(); // return 5, the student sits at the last seat number 5.



&nbsp;
Constraints:


	1 &lt;= n &lt;= 109
	It is guaranteed that there is a student sitting at seat p.
	At most 104 calls will be made to seat and leave.


class ExamRoom:

    def __init__(self, n: int):
        self.N = n
        self.pq = []
        self.dict = {}
        self.addSegment(0, self.N - 1)

    def seat(self) -> int:
        start, end, distance = heapq.heappop(self.pq)
        self.dict.pop(start, None) #Remove old segment from dictionary
        self.dict.pop(end, None)

        if start == end:
            position = start

        elif start == 0:
            position = start
            right = self.addSegment(start + 1, end)

        elif end == self.N - 1:
            position = end
            left = self.addSegment(start, end - 1)

        elif end - start == 1: #ONLY ONE PLACE TO PUT
            position = start
            left = self.addSegment(start + 1, end)

        else:
            position = start + (end - start) // 2
            right = self.addSegment(start, position - 1)
            left = self.addSegment(position + 1, end)

        return position

    def leave(self, p: int) -> None:
        left = self.dict.get(p - 1, None)
        right = self.dict.get(p + 1, None)

        new_start = new_end = p

        if left:
            self.removeSegment(left)
            new_start = left.start

        if right:
            self.removeSegment(right)
            new_end = right.end

        self.addSegment(new_start, new_end)

    def addSegment(self, start, end):
            segment = Segment(start, end, self.N)
            self.dict[segment.start] = segment
            self.dict[segment.end] = segment
            heapq.heappush(self.pq, segment)

    def removeSegment(self, segment):
            self.dict.pop(segment.start, None)
            self.dict.pop(segment.end, None)
            self.pq.remove(segment)

class Segment():
    def __init__(self, start, end, N):
        self.start = start
        self.end = end
        self.distance = self.calculateDistance(start, end, N)

    def __lt__(self, other_segment):
        return self.distance > other_segment.distance if self.distance != other_segment.distance else self.start < other_segment.start

    def calculateDistance(self, start, end, N):
        if start == 0:
            return end

        if end == N - 1:
            return end - start

        else:
            return (end - start) // 2

    def __iter__(self):
        return iter((self.start, self.end, self.distance))
class ExamRoom {

    private final int max;
    private final TreeSet<Interval> available;
    private final TreeSet<Integer> taken;

    public ExamRoom(int n) {
        this.max = n - 1;
        this.available = new TreeSet<>((a, b) -> {
            var distA = getMinDistance(a);
            var distB = getMinDistance(b);
            return distA == distB ? a.s - b.s : distB - distA;
        });
        this.available.add(new Interval(0, max));
        this.taken = new TreeSet<>();
    }

    public int seat() {
        var inter = available.pollFirst();
        var idx = getInsertPosition(inter);
        taken.add(idx);
        if ((idx - 1) - inter.s >= 0)
            available.add(new Interval(inter.s, idx - 1));
        if (inter.e - (idx + 1) >= 0)
            available.add(new Interval(idx + 1, inter.e));
        return idx;
    }

    public void leave(int p) {
        taken.remove(p);
        var lo = taken.lower(p);
        if (lo == null)
            lo = -1;
        var hi = taken.higher(p);
        if (hi == null)
            hi = max + 1;
        available.remove(new Interval(lo + 1, p - 1));
        available.remove(new Interval(p + 1, hi - 1));
        available.add(new Interval(lo + 1, hi - 1));
    }

    private int getInsertPosition(Interval inter) {
        if (inter.s == 0)
            return 0;
        else if (inter.e == max)
            return max;
        else
            return inter.s + (inter.e - inter.s) / 2;
    }

    private int getMinDistance(Interval in) {
        return in.s == 0 || in.e == max ? in.e - in.s : (in.e - in.s) / 2;
    }

    private final class Interval {
        private final int s;
        private final int e;

        Interval(int s, int e) {
            this.s = s;
            this.e = e;
        }

        @Override
        public String toString() {
            return "[" + s + "," + e + "]";
        }
    }
}
class ExamRoom {
public:
    set<int> s;  // ordered set
    int num;
    ExamRoom(int n) {
        num=n;    // total seats
    }
    
    int seat() {
        if(s.size()==0) { s.insert(0); return 0;}     // if size is zero place at seat 0
        auto itr = s.begin();
        if(s.size()==1) {                                      // if size==1 -> check if its closer to 0 or last seat (num-1) 
            if(*itr > num-1-(*itr)){ s.insert(0); return 0; }
              else{  s.insert(num-1); return num-1;}
        }
        int mx=-1;     // for max gap
        int l=0;          // for left index of the student to max gap.
        
        if(s.find(0)==s.end()){mx = (*itr); l=-mx;}    // if 0 is not seated -> check gap with 0 and starting seat.
		
		// Iterate the set to calculate gaps 
        for(int i=0;i<s.size()-1;i++)
        {
           int a=*itr;    // seat number  for 1st element 
           itr++;
           int b = *itr;   // seat number of next element in the set
		   
		   // check the gap and update
           if(mx<(b-a)/2){
               mx=(b-a)/2;
               l=a;
           }
        }
        if(s.find(num-1)==s.end()) {   // if last seat is vacant -> check gap with last filled seat and (num-1)
           if(mx< num-1-(*itr)) {
               mx = (num-1-(*itr));
               l=*itr;
           }
        }
        s.insert(l+mx);   // place the student at l+mx
        return l+mx;
        
        
    }
    
    void leave(int p) {
	// remove student from set
        s.erase(p);
    }
};
/**
 * @param {number} n
 */
var ExamRoom = function(n) {
    this.n = n
    this.list = []
};

/**
 * @return {number}
 */
ExamRoom.prototype.seat = function() {
    // if nothing in the list, seat the first student at index 0.
    if(this.list.length === 0){
        this.list.push(0)
        return 0
    }

    // find the largest distance between left wall and first student, and right wall and last student
    let distance = Math.max(this.list[0], this.n - 1 - this.list[this.list.length-1])
    // update the largest distance by considering the distance between students
    for(let i=0; i<this.list.length-1; i++){
        distance = Math.max(distance, Math.floor((this.list[i+1] - this.list[i]) / 2))
    }

    // in case the largest distance is between left wall and first student, we seat next student at the left wall
    if(distance === this.list[0]){
        this.list.unshift(0)
        return 0
    }

    // in case the largest distance is between two student, we seat the next student in between these two students
    for(let i=0; i<this.list.length-1; i++){
        if(distance === Math.floor( (this.list[i+1]-this.list[i])/2 )){
            let insertIndex = Math.floor( (this.list[i+1]+this.list[i]) / 2 )
            this.list.splice(i+1,0, insertIndex)
            return insertIndex
        }
    }

    // in case the largest distance is between the last student and the right wall, we seat the next student at the right wall
    this.list.push(this.n-1)
    return this.n - 1
};

/**
 * @param {number} p
 * @return {void}
 */
ExamRoom.prototype.leave = function(p) {
    // We iterate through the list and find the index where the student p sit at, then remove that index.
    for(let i=0; i<this.list.length; i++){
        if(this.list[i] === p) {
            this.list.splice(i, 1)
            break
        }
    }
};

/**
 * Your ExamRoom object will be instantiated and called as such:
 * var obj = new ExamRoom(n)
 * var param_1 = obj.seat()
 * obj.leave(p)
 */
Exam Room