Java TreeSet both operation O(log n)
Some people use PriorityQueue to slove this problem, storing interval with descending dist order.\nBut priority queue takes O(n) to delete element.\nSo i wonder
Some people use PriorityQueue to slove this problem, storing interval with descending dist order.\nBut priority queue takes O(n) to delete element.\nSo i wonder if we could use treeSet that could take advantage of sorting and deleting by O(logn)\n\nWe need two treeSet, one is for storing Interval called heap\none is for storing occupied seat.\n\nWhen seat(), we find interval with largest dist and divide it by half, return mid point as seat.\n\nWhen leave(int p), we find occupied seats before p and after p, and reconstruct two intervals, delete them from heap, add merged Interval into it, and also delete p from occupied seats.\n\nNote: for seat at 0 and at N-1, we add dummy seat -1 and N, and for Interval class, if we get start as -1, we know the dist should be end. If we get end as N, we know the dist should be N - 1 - s.\n\nWe also need to override equals insde interval class for deleting purpose.\n```\nclass ExamRoom {\n  TreeSet<Interval> heap;\n  TreeSet<Integer> seats;\n  int N;\n  public ExamRoom(int N) {\n    heap = new TreeSet<>((a, b) -> {\n      if (a.dist == b.dist) {\n        return a.s - b.s;\n      }\n      return b.dist - a.dist;\n    });\n    seats = new TreeSet<>();\n    this.N = N;\n    heap.add(new Interval(-1, N));\n    seats.add(-1);\n    seats.add(N);\n  }\n    \n  public int seat() {\n    Interval in = heap.first();\n    heap.remove(in);\n    int div = (in.s + in.e) / 2;\n    if (in.s == -1) {\n      div = 0;\n    } else if (in.e == N) {\n      div = N - 1;\n    }\n    \n    Interval left = new Interval(in.s, div);\n    Interval right = new Interval(div, in.e);\n    heap.add(left);\n    heap.add(right);\n    seats.add(div);\n    return div;\n  }\n    \n  public void leave(int p) {\n    int left = seats.lower(p);\n    int right = seats.higher(p);\n    heap.remove(new Interval(left, p));\n    heap.remove(new Interval(p, right));\n    seats.remove(p);\n    \n    heap.add(new Interval(left, right));\n  }\n  \n  private class Interval {\n    int s;\n    int e;\n    int dist;\n    \n    public Interval(int s, int e) {\n      this.s = s;\n      this.e = e;\n      if (s == -1) {\n        this.dist = e;\n      } else if (e == N) {\n        this.dist = N - 1 - s;\n      } else {\n        this.dist = (this.e - this.s) / 2;\n      }\n    }\n    \n    @Override \n    public boolean equals(Object o) {\n      if (o == this) {\n        return true;\n      }\n      if (!(o instanceof Interval)) {\n        return false;\n      }\n      Interval in = (Interval) o;\n      return this.s == in.s && this.e == in.e;\n    }\n  }\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```
[]