Python seat logN, leave logN solution
The idea is to maintain valid intervals in the dictionary d. Key is seat and value is intervals that contain key. For example, students have seats 0,4,9, then t
The idea is to maintain valid intervals in the dictionary d. Key is seat and value is intervals that contain key. For example, students have seats 0,4,9, then the dictionary with valid intervals is\n```\nintervals = {0:{(0,4)}, 4:{(0,4),(4,9)}, 9:{(4,9)}}\n```\nEvery value in intervals is the set of length at most 2 because whenever we placing or evicting a student, we maintain the intervals (merging intervals or removing invalid ones) \n\nThere is also priority queue here. It conains the entry of distance, x, y where distance either  y-x//2 or y-x (we use this ditance only if placing the student at 0 or n-1 place)\n\n```\nclass ExamRoom:\n\n    def __init__(self, n: int):\n        self.intervals = collections.defaultdict(set)\n        self.pq = [(0, 0, n - 1)]\n        self.intervals[0].add((0, n - 1))\n        self.n = n\n        self.zeroDeleted = True\n        self.nDeleted = True\n\n    def seat(self) -> int:\n\n        while self.pq:\n            dist, i, j = heapq.heappop(self.pq)\n            if (i, j) not in self.intervals[i]:\n                continue\n            break\n\n        if self.zeroDeleted and i == 0:\n            self.zeroDeleted = False\n            mid = 0\n            self.putrigh(mid, j)\n        elif self.nDeleted and j == self.n - 1:\n            self.nDeleted = False\n            mid = self.n - 1\n            self.putleft(i, mid)\n        else:\n            mid = (i + j) // 2\n            self.putleft(i, mid)\n            self.putrigh(mid, j)\n\n        return mid\n\n    def putleft(self, i, mid):\n        heapq.heappush(self.pq, (-((mid - i) // 2), i, mid))\n        self.cleanupleft(i, mid)\n        self.cleanupright(i, mid)\n\n    def putrigh(self, mid, j):\n        heapq.heappush(self.pq, (-((j - mid) // 2), mid, j))\n        self.cleanupleft(mid, j)\n        self.cleanupright(mid, j)\n\n    def cleanupleft(self, key, y):\n        to_evict = set([(i, j) for i, j in self.intervals[key] if i == key])\n        self.intervals[key] = self.intervals[key].difference(to_evict)\n        self.intervals[key].add((key, y))\n\n    def cleanupright(self, x, key):\n        to_evict = set([(i, j) for i, j in self.intervals[key] if j == key])\n        self.intervals[key] = self.intervals[key].difference(to_evict)\n        self.intervals[key].add((x, key))\n\n    def leave(self, p: int) -> None:\n        vals = sorted(self.intervals[p])\n        l = vals[0][0]\n        r = vals[0][1]\n        if p == 0:\n            self.zeroDeleted = True\n            heapq.heappush(self.pq, (-(r - l), l, r))\n            self.cleanupright(p, r)\n            self.cleanupleft(p, r)\n        elif p == self.n - 1:\n            self.nDeleted = True\n            heapq.heappush(self.pq, (-(r - l), l, r))\n            self.cleanupright(l, p)\n            self.cleanupleft(l, p)\n        else:\n            l = vals[0][0]\n            r = vals[1][1]\n            self.cleanupleft(l, r)\n            self.cleanupright(l, r)\n            if (self.zeroDeleted and l == 0) or (self.nDeleted and r == self.n - 1):\n                heapq.heappush(self.pq, (-(r - l), l, r))\n            else:\n                heapq.heappush(self.pq, (-((r - l) // 2), l, r))\n            self.intervals.pop(p)\n```
['Heap (Priority Queue)', 'Python', 'Python3']