Clean Python Solution
This is question is similar to 849. Maximize Distance to Closest Person. Additionally, we need to know where Alex will take a seat (suppose choose the smaller i
This is question is similar to [849. Maximize Distance to Closest Person](https://leetcode.com/problems/maximize-distance-to-closest-person/). Additionally, we need to know where Alex will take a seat (suppose choose the smaller index when same maximum distances exist).\n\n\n```python\nclass Solution:\n    def maxDistToClosest(self, seats: List[int]) -> int:\n        n = len(seats)\n        start = -1\n        res = 0\n        seat = -1\n        for i in range(n):\n            if seats[i] == 0:\n                continue\n            if start == -1:\n                if i > res:\n                    res = i\n                    seat = 0\n            else:\n                if (i-start)//2 > res:\n                    res = (i-start)//2\n                    seat = (i+start)//2\n            start = i\n        if n-1-start > res:\n            res = n-1-start\n            seat = n-1\n        print("Alex will seat here: %d" % seat)\n        return res\n```\n\nSo we can follow the same method. In order to save more space, we just apply a list to record the index of non-empty seats.\n\n```python\nclass ExamRoom:\n\n    def __init__(self, N: int):\n        self.seats = []\n        self.total = N\n\n    def seat(self) -> int:\n        n = self.total\n        start = -1\n        idx = -1\n        mx = 0\n    \n        for i in self.seats:\n            if start == -1:\n                if i > mx:\n                    mx = i\n                    idx = 0\n            else:\n                if (i-start)//2 > mx:\n                    mx = (i-start)//2\n                    idx = (i+start)//2\n            start = i\n       \t\n        if start != -1:\n            if n-1-start > mx:\n                mx = n-1-start\n                idx = n-1\n        else:\n            idx = 0\n        \n        bisect.insort(self.seats, idx)\n        return idx\n\n    def leave(self, p: int) -> None:\n        self.seats.remove(p)\n        \n# Your ExamRoom object will be instantiated and called as such:\n# obj = ExamRoom(N)\n# param_1 = obj.seat()\n# obj.leave(p)\n```\n\nWe can apply Binary Search to speed up the insert and delete process.\n\n```python\nclass ExamRoom:\n\n    def __init__(self, N: int):\n        self.seats = []\n        self.total = N\n\n    def seat(self) -> int:\n        n = self.total\n        start = -1\n        idx = -1\n        mx = 0\n    \n        for i in self.seats:\n            if start == -1:\n                if i > mx:\n                    mx = i\n                    idx = 0\n            else:\n                if (i-start)//2 > mx:\n                    mx = (i-start)//2\n                    idx = (i+start)//2\n            start = i\n       \t\n        if start != -1:\n            if n-1-start > mx:\n                mx = n-1-start\n                idx = n-1\n        else:\n            idx = 0\n        \n        j = self.search(self.seats, idx)\n        self.seats.insert(j+1, idx)\n        \n        return idx\n\n    def leave(self, p: int) -> None:\n        j = self.search(self.seats, p)\n        self.seats.pop(j+1)\n    \n    # find the largest index < target in a sorted array\n    def search(self, nums, target):\n        if len(nums) == 0:\n            return -1\n        \n        start, end = 0, len(nums)-1\n        while start+1 < end:\n            mid = start+(end-start)//2\n            if nums[mid] < target:\n                start = mid\n            else:\n                end = mid\n        if nums[end] < target:\n            return end\n        if nums[start] < target:\n            return start\n        return -1\n        \n# Your ExamRoom object will be instantiated and called as such:\n# obj = ExamRoom(N)\n# param_1 = obj.seat()\n# obj.leave(p)\n```
[]