[Java] Two TreeSets Solution. Both Seat and Leave O(log n) Time Complexity
I was inspired by this solution. Please upvote his solution as well! Credit to @wangdeve.\n\nIn leave(seat) operation, we could take advantage of higher(seat) a
I was inspired by this [solution](https://leetcode.com/problems/exam-room/discuss/148595/Java-PriorityQueue-with-customized-object.-seat:-O(logn)-leave-O(n)-with-explanation). Please upvote his solution as well! Credit to [@wangdeve](https://leetcode.com/wangdeve "User").\n\nIn leave(seat) operation, we could take advantage of `higher(seat)` and `lower(seat)` methods in `TreeSet` to get the start and end position of the new merged interval.\n\n```\nclass ExamRoom {\n    // O(logn) seat, O(logn) leave, n is the size of treesets.\n    private TreeSet<Integer> takenSeats;\n    private TreeSet<Interval> descIntervals;\n    private int N;\n    \n    class Interval {\n        int x, y, dis;\n        String id; // for O(1) lookup\n\n        public Interval(int x, int y) {\n            this.x = x;\n            this.y = y;\n            if (x == -1) {\n                this.dis = y;\n            } else if (y == N) {\n                this.dis = N - 1 - x;\n            } else {\n                this.dis = Math.abs(x - y) / 2; // works for both odd and even distance. The dis is to the closest person, no matter on the left or right.\n            }\n            this.id = x + "_" + y;\n        }\n\n        // this is for TreeSet remove (Object o) method.\n        public boolean equals(Interval i) {\n            return this.id.equals(i.id);\n        }\n    }\n\n    public ExamRoom(int N) {\n        this.takenSeats = new TreeSet<>();\n        this.descIntervals = new TreeSet<>((a, b) -> a.dis != b.dis ? b.dis - a.dis : a.x - b.x);\n        this.N = N;\n        this.descIntervals.add(new Interval(-1, N));\n    }\n    \n\t// O(log n) time complexity with TreeSet add methods\n    public int seat() {\n        int pos = 0;\n        Interval interval = this.descIntervals.pollFirst();\n        if (interval.x == -1) {\n            descIntervals.add(new Interval(0, interval.y));\n        } else if (interval.y == this.N) {\n            pos = N - 1;\n            descIntervals.add(new Interval(interval.x, N - 1));\n        } else {\n            pos = interval.x + (interval.y - interval.x) / 2;\n            descIntervals.add(new Interval(interval.x, pos));\n            descIntervals.add(new Interval(pos, interval.y));\n        }\n        this.takenSeats.add(pos);\n        return pos;\n    }\n    \n\t// O(log n) time complexity. TreeSet lower, higher, remove and add methods all have O(log n) time complexity.\n    public void leave(int p) {\n        int startIndex = this.takenSeats.lower(p) == null ? -1 : this.takenSeats.lower(p);\n        int endIndex = this.takenSeats.higher(p) == null ? N : this.takenSeats.higher(p);\n        mergeIntervals(new Interval(startIndex, p), new Interval(p, endIndex), this.descIntervals);\n        this.takenSeats.remove(p);\n    }\n    \n    // Time complexity of add and remove operations in TreeSet is O(log n)\n    private void mergeIntervals(Interval i1, Interval i2, TreeSet<Interval> descIntervals) {\n        descIntervals.remove(i1);\n        descIntervals.remove(i2);\n        descIntervals.add(new Interval(i1.x, i2.y));\n    }\n}\n```
[]