Python heap solution with idea explanation
The basic idea is to use a heap to give access to the largest distance.\nThe item in the heap is [-distance, left, right, valid]\nleft and right are the most le
The basic idea is to use a heap to give access to the largest distance.\nThe item in the heap is [-distance, left, right, valid]\nleft and right are the most left and the most right empty space for a empty segment.\nUse a dict to support the random access to items in heap, (left, right):[-distance, left, right, valid]\nthe distance is right-left if either left or right is the left boundary or right boundary of the class room\notherwise the distance is (right-left)//2\nthe valid is a flag to denote if this item is valid or not. Later in leave(), we do not delete items in heap, but set the flag to False.\nDuring seat(), we will continues to heappop if the heap top is not valid.\nDuring leave(), we try to find the two segments adjacent to p. And then create a merged segment.\n```\nimport heapq\nclass ExamRoom:\n    def __init__(self, N: int):\n        self.heap_dict = {(0,N-1):[-N, 0, N-1, True]} # By this dict we have direct access to any items in heap\n        self.my_heap = [self.heap_dict[(0,N-1)]]\n        self.last = N-1\n        \n    def seat(self) -> int:\n        left = right = 0\n        while self.my_heap:\n            _, left, right, valid = heappop(self.my_heap)\n            if valid:\n                break\n        pos = self.helper(left, right)\n        if pos > left:\n            dis = (pos - 1 - left)//2\n            self.heap_dict[(left, pos-1)] = [-dis, left, pos-1, True]\n            heappush(self.my_heap, self.heap_dict[(left, pos-1)])\n        if pos < right:\n            dis = (right - (pos+1))//2\n            self.heap_dict[(pos+1, right)] = [-dis, pos+1, right, True]\n            heappush(self.my_heap, self.heap_dict[(pos+1, right)])\n        return pos\n        \n    def helper(self, left, right):\n        if left == 0:\n            return left\n        if right == self.last:\n            return right\n        return left + (right-left)//2\n        \n    def leave(self, p: int) -> None:\n        left = right = p\n        for obj in self.my_heap:\n            if obj[2] == p-1 and obj[3]:\n                left = obj[1]\n                self.heap_dict[(obj[1], obj[2])][3] = False # find the left segment to merge\n            if obj[1] == p+1 and obj[3]:\n                right = obj[2]\n                self.heap_dict[(obj[1], obj[2])][3] = False # find the right segment to merge\n        dis = (right - left)//2\n        if left == 0 or right == self.last:\n            dis = right - left\n        self.heap_dict[(left, right)] = [-dis, left, right, True]\n        heappush(self.my_heap, self.heap_dict[(left, right)])\n```
[]