Java clean O(log n) seat O(log n) leave
Use a TreeMap to find longest distance between students\nUse a HashMap to find distance to previous/next student\n\nTreeMap lastKey() is O(long n), no need to t
Use a TreeMap to find longest distance between students\nUse a HashMap to find distance to previous/next student\n\nTreeMap lastKey() is O(long n), no need to traverse the whole tree\n```\nclass ExamRoom {\n    private int n,sift=1000_000_000;\n    private Map<Integer,int[]>m;\n    private TreeMap<Long,Integer>map;\n    public ExamRoom(int N) {\n        m=new HashMap<>();\n        map=new TreeMap<>();\n        n=N;\n        m.put(-1,new int[]{0,n+1});\n        m.put(n,new int[]{n+1,0});\n        map.put(hs(n+1,n+1),-1);\n    }\n    private long hs(int l,int p){\n        return (long)l/2*sift+p;\n    }\n    public int seat() {\n        if(m.size()==n+2)return -1;\n        long val = map.lastKey();\n        int next = map.get(val);\n        int[]ra=m.get(next),rn=m.get(ra[1]+next);\n        int l=ra[1]/2;\n        if(next == -1) l=1;\n        else if(ra[1]+next==n) l=ra[1]-1;\n        int r=ra[1]-l,newSeat=next+l;\n        m.put(newSeat,new int[]{l,r});\n        map.remove(val);\n        if(l>1) map.put(hs(l,n-next),next);\n        if(r>1) map.put(hs(r,n-newSeat),newSeat);\n        ra[1]=l;\n        rn[0]=r;\n        return newSeat;\n    }\n    \n    public void leave(int p) {\n        int []ra=m.get(p);\n        int prev=p-ra[0],next=p+ra[1];\n        int[] l = m.get(prev),r=m.get(next);\n        l[1]=ra[0]+ra[1];\n        r[0]=ra[0]+ra[1];\n        if(l[0]==0) map.remove(hs((ra[0]-1)*2,n-prev));\n        else if(ra[0]>1) map.remove(hs(ra[0],n-prev));\n        if(r[1]==0) map.remove(hs((ra[1]-1)*2,n-p));\n        else if(ra[1]>1) map.remove(hs(ra[1],n-p));\n        m.remove(p);\n        if(r[1]==0 || l[0]==0)map.put(hs((ra[0]+ra[1]-1)*2,n-prev),prev);\n        else map.put(hs(ra[0]+ra[1],n-prev),prev);\n    }\n}\n```\nIn my local benchmark with 100000 ops, priorityQueue solution gets 11547ms\nThis solution gets 73ms\n\nIt tells the time complexity
[]