Using sorted list O(log n) solution
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\nTo solve this problem, we need to implement an ExamRoom class that effect
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\nTo solve this problem, we need to implement an ExamRoom class that effectively manages seat assignments to maximize the distance between students and properly handles students leaving. Here\'s how we can achieve that:\n\n### Key Insights:\nMaximize Distance: When a student enters, they should sit in the seat that maximizes the distance to the closest person. If multiple seats have the same distance, the seat with the lower index should be chosen.\n\nEfficient Management: We\'ll use a sorted list to keep track of the positions of occupied seats. This will allow us to efficiently find the seat that maximizes the distance to the closest person.\n\nHandling Leaving: When a student leaves, we need to remove their seat from the occupied seats list and maintain the order of the list.\n\nData Structures:\nSorted List: To maintain the positions of occupied seats in order.\nSet: For O(1) time complexity on checking if a seat is occupied.\n\nHere\'s the implementation:\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nimport bisect\n\nclass ExamRoom:\n\n    def __init__(self, n: int):\n        self.n = n\n        self.students = []\n\n    def seat(self) -> int:\n        if not self.students:\n            student = 0\n        else:\n            max_dist = self.students[0]\n            student = 0\n            for i in range(1, len(self.students)):\n                prev = self.students[i - 1]\n                curr = self.students[i]\n                dist = (curr - prev) // 2\n                if dist > max_dist:\n                    max_dist = dist\n                    student = prev + dist\n            \n            # Check the last position\n            if self.n - 1 - self.students[-1] > max_dist:\n                student = self.n - 1\n        \n        bisect.insort(self.students, student)\n        return student\n\n    def leave(self, p: int) -> None:\n        self.students.remove(p)\n        \n\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\n\nExplanation:\n\nInitialization: In the constructor (__init__), we initialize the n and an empty list students to keep track of occupied seats.\n\nSeating (seat method):\nIf no students are seated, the first student sits at seat 0.\nFor each pair of adjacent occupied seats, calculate the midpoint and update the seat to maximize the distance.\nCheck the last seat separately because it might offer the largest distance.\nInsert the chosen seat into the sorted list using bisect.insort for maintaining the order.\n\nLeaving (leave method):\nSimply remove the seat from the list of occupied seats.\nThis approach ensures efficient seat assignment and removal with a time complexity of \n\uD835\uDC42(log \uD835\uDC5B) for both seating and leaving operations due to the use of the sorted list.
['Python3']