log(n)
Intuition\n Describe your first thoughts on how to solve this problem. \n- Maintain occupied pos and interval in the set. \n- Add a very large interval in the s
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n- Maintain occupied pos and interval in the set. \n- Add a very large interval in the starting to handle edge cases. \n- If an interval lower or higher boundary does not exist, person will be placed on either of the boundary otherwise in the middle of interval. \n- Add this handling in the comparator as well.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity: logn\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(n)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass ExamRoom {\n    TreeSet<int[]> intervals;\n    TreeSet<Integer> pos;\n    int n;\n    public ExamRoom(int n) {\n        intervals = new TreeSet<int[]>((a,b)->compare(a,b));\n        pos = new TreeSet<>();\n        pos.add(Integer.MIN_VALUE);\n        pos.add(Integer.MAX_VALUE);\n        intervals.add(new int[]{Integer.MIN_VALUE,Integer.MAX_VALUE});\n        this.n = n;\n    }\n    int[] getInterval(int[]a){\n        int low = Math.max(a[0],0);\n        int high = Math.min(a[1],n-1);\n        if(a[0]==Integer.MIN_VALUE || a[1]==Integer.MAX_VALUE){\n            return new int[]{(high-low),low};\n        }\n        return new int[]{(high-low)/2,low};\n    }\n    int compare(int[]a, int b[]){\n        int [] r1 = getInterval(a);\n        int [] r2 = getInterval(b);\n        if(r1[0]!=r2[0]){\n            return r2[0] - r1[0];\n        }\n        return r1[1] - r2[1];\n    }\n    \n    public int seat() {\n        int [] interval = intervals.first();\n        int seat = seatPos(interval);\n        intervals.remove(interval);\n        pos.add(seat);\n        intervals.add(new int[]{interval[0],seat});\n        intervals.add(new int[]{seat,interval[1]});\n        return seat;\n    }\n    \n    public void leave(int p) {\n        int lower = pos.lower(p);\n        int upper = pos.higher(p);\n        pos.remove(p);\n        intervals.remove(new int[]{lower,p});\n        intervals.remove(new int[]{p,upper});\n        intervals.add(new int[]{lower,upper});\n    }\n    int seatPos(int[]a){\n        if(a[0]==Integer.MIN_VALUE){\n            return 0;\n        }\n        if(a[1]==Integer.MAX_VALUE){\n            return n-1;\n        }\n        return (a[0]+a[1])/2;\n    }\n}\n\n/**\n * Your ExamRoom object will be instantiated and called as such:\n * ExamRoom obj = new ExamRoom(n);\n * int param_1 = obj.seat();\n * obj.leave(p);\n */\n```\n
['Java']