Prettiest solution
Intuition\n Describe your first thoughts on how to solve this problem. \nWe use a treeset to maintain the order of gaps created each time when inserting a perso
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nWe use a treeset to maintain the order of gaps created each time when inserting a person , in form of arrays those gaps will be sorted in decreasing order with left and right index where left index is sorted in inceasing order because when the gap distance is equal we will return the position with the smallest label .\n\nIitially , we add to the treeMap [-1 ,n] and \nif left==-1=> pos=0 \nelse if right=n => pos=n-1\nelse calculate the mid of the top gap in the treeMap\n\nWhen removing a person at position p we need to remove the 2 gaps created when inserting this person   : \ntreeMap.remove( [leftp,p] ) && treeMap.remove( [p,rightp] ) those left and right indexes will be retrieved from 2 maps we created earlier each map defines respecively the nearest left neighbour for p and nearest right neighbour for p . now after removing the 2 gaps we add the new gap [leftp,rightp]\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\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```\npublic class ExamRoom {\n    private TreeSet<int[]> seatSet = new TreeSet<>(\n        (a, b) -> {\n            int distanceA = calculateDistance(a);\n            int distanceB = calculateDistance(b);\n            // Compare by distance, then by starting index if distances are equal\n            return distanceA == distanceB ? a[0] - b[0] : distanceB - distanceA;\n        }\n    );\n    // Maps to track the nearest occupied seat to the left and right of each seat\n    private Map<Integer, Integer> leftNeighbour = new HashMap<>();\n    private Map<Integer, Integer> rightNeighbour = new HashMap<>();\n    private int seatCount;\n\n    public ExamRoom(int n) {\n        this.seatCount = n;\n        // Initialize with a dummy seat segment representing the whole row\n        add(new int[] {-1, seatCount});\n    }\n\n    public int seat() {\n        // Get the seat segment representing the largest distance between seated students\n        int[] segment = seatSet.first();\n        int seatPosition = (segment[0] + segment[1]) / 2;\n        // Handle cases where we need to seat at the start or the end\n        if (segment[0] == -1) {\n            seatPosition = 0;\n        } else if (segment[1] == seatCount) {\n            seatPosition = seatCount - 1;\n        }\n        // Remove the current segment and add new segments reflecting the new student being seated\n        remove(segment);\n        add(new int[] {segment[0], seatPosition});\n        add(new int[] {seatPosition, segment[1]});\n        return seatPosition;\n    }\n\n    public void leave(int p) {\n        // Find the immediate neighbours of the leaving student\n        int leftIndex = leftNeighbour.get(p);\n        int rightIndex = rightNeighbour.get(p);\n        // Remove the segments created by the leaving student\n        remove(new int[] {leftIndex, p});\n        remove(new int[] {p, rightIndex});\n        // Create a new segment reflecting the gap left by the student\n        add(new int[] {leftIndex, rightIndex});\n    }\n\n    private int calculateDistance(int[] segment) {\n        int l = segment[0], r = segment[1];\n        // For seats at the beginning or end, use the whole distance minus one\n        if (l == -1 || r == seatCount) {\n            return r - l - 1;\n        } else {\n            // Else, use the half the distance between l and r\n            return (r - l) / 2;\n        }\n    }\n\n    private void add(int[] segment) {\n        seatSet.add(segment);\n        leftNeighbour.put(segment[1], segment[0]);\n        rightNeighbour.put(segment[0], segment[1]);\n    }\n\n    private void remove(int[] segment) {\n        seatSet.remove(segment);\n        leftNeighbour.remove(segment[1]);\n        rightNeighbour.remove(segment[0]);\n    }\n}\n```
['Hash Table', 'Java']