Java Double TreeSet the Cleanest Both O(logn) Solution
Intuition\n Describe your first thoughts on how to solve this problem. \nCapture all the "gaps" between occupied seat pairs. With each pair of seat ids we can c
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nCapture all the "gaps" between occupied seat pairs. With each pair of seat ids we can compute the minimum distance to neighbouring students after seating as well as the new target seat id.\n# Approach\n<!-- Describe your approach to solving the problem. -->\nWith ordered set, sort all intervals by minimum distance to others after seating in descending order. Compare interval start seat id for ties on minimum distance. Implementing Comparable interface along with extracting the getSeatId() in Interval class is the key to clean up the seat() and leave() method.\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO(logn) for both seat() and leave()\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(n)\n# Code\n```\nclass ExamRoom {\n\n\tTreeSet<Integer> seated;//ordered by id, needed for leave()\n\tTreeSet<Interval> intervals;//ordered by min distance after seating within the interval\n\tint n;\n    public ExamRoom(int n) {\n        seated = new TreeSet<Integer>();\n        seated.add(-1);seated.add(n);\n        intervals = new TreeSet<Interval>();\n        intervals.add(new Interval(-1, n, n));\n        this.n = n;\n    }\n\n    public int seat() {\n    \tInterval inter = intervals.first();\n    \tint id = inter.getSeatId();\n    \tseated.add(id);\n    \tintervals.remove(inter);\n    \tintervals.add(new Interval(inter.left, id,n));\n    \tintervals.add(new Interval(id, inter.right,n));\n    \treturn id; \n    }\n\n    public void leave(int p) {\n    \tint l = seated.lower(p);\n    \tint h = seated.higher(p);\n    \tseated.remove(p);\n    \tintervals.remove(new Interval(l,p,n));\n    \tintervals.remove(new Interval(p,h,n));\n    \tintervals.add(new Interval(l,h,n));\n    }\n}\n\nclass Interval implements Comparable<Interval>\n{\n\tint n;\n\tint left, right;//seat id of left and right end of interval, both should be seated\n\tpublic Interval(int left, int right, int n)\n\t{\n\t\tthis.left = left;\n\t\tthis.right = right;\n\t\tthis.n = n;\n\t}\n\n\t@Override\n\tpublic int compareTo(Interval that) {\n\t\t//if minD equals, we check id\n\t\tint thisD = this.minD(), thatD = that.minD();\n\t\t\n\t\treturn thisD == thatD? this.left - that.left : thatD - thisD;\n\t}\n\t\n\tint minD()\n\t{\n\t\tif(left == -1 || right == n || right - left == 1)\n\t\t\treturn right - left - 2;\n\t\treturn (right - left - 2) / 2;\n\t}\n\t\n\tint getSeatId()\n\t{\n\t\tif(left == -1)\n\t\t\treturn 0;\n\t\tif(right == n)\n\t\t\treturn n - 1;\n\t\treturn (left + right) / 2;\n\t}\n}\n```
['Ordered Set', 'Java']