Pyhton Solution using Heaps
Solution Intuition - \n\nKeep track of the following data structure. A heap of ([ left-right, left,right]) called stack in the code below, where the students ar
Solution Intuition - \n\nKeep track of the following data structure. A heap of ([ left-right, left,right]) called stack in the code below, where the students are currently in positions left and right. \n\nOn arrival of a student, sample from this min-heap and place the new student in the middle of left and right. Some care needs to be taken in case of boundary cases.\n\nTo remove a student, observe that each removed position occurs at-most twice in this heap. So, we remove those two entries and replace it by a contiguous single element in the heap. Again, little care is needed to handle the boundary conditions.\n\nPlease comment and let me know if the code is unclear or needs more explanation.\n\n\n```\nclass ExamRoom(object):\n\n    def __init__(self, N):\n        """\n        :type N: int\n        """\n        self.stack = []\n        self.N = N\n        \n\n    def seat(self):\n        """\n        :rtype: int\n        """\n     \n        if len(self.stack) == 0:\n            heapq.heappush(self.stack,[-int((2*self.N-1)/2),0,2*self.N-1])\n            return 0\n        else:\n            top_width = heapq.heappop(self.stack)\n            left = top_width[1]\n            right = top_width[2]\n            if top_width[0]==0:\n                return -1\n            if 0 <= left < right <= self.N-1:\n                idd = int((left+right)/2)\n                heapq.heappush(self.stack,[-int((idd-left)/2),left,idd])\n                heapq.heappush(self.stack,[-int((right-idd)/2),idd,right])\n                return idd\n            if left < 0:\n                heapq.heappush(self.stack,[-int((right)/2),0,right])\n                return 0\n            if right > self.N-1:\n                heapq.heappush(self.stack,[-int((self.N-1-left)/2),left,self.N-1])\n                return self.N-1\n      \n\n    def leave(self, p):\n        """\n        :type p: int\n        :rtype: None\n        """\n        temp = []\n        nr = self.N+1\n        nl = -1\n        while len(self.stack) > 0:\n            c_seat = heapq.heappop(self.stack)\n           \n            if c_seat[1] == p :\n                nr = c_seat[2]\n                continue\n            elif c_seat[2] == p:\n                nl = c_seat[1]\n                continue\n            else:\n                heapq.heappush(temp,c_seat)\n       \n        if nl < 0 and nr < self.N:\n            nl = -nr\n        elif nl >=0 and nr > self.N-1:\n            nr = (2*(self.N-1))-nl\n        \n        n_seat = [-int((nr-nl)/2),nl,nr]\n        heapq.heappush(temp,n_seat)\n        while len(temp) > 0:\n            c_node = heapq.heappop(temp)\n            heapq.heappush(self.stack,c_node)\n        \n```
[]