[ JAVA ] without sorting queries using segment tree
I sorted rooms according to increasing order of their id and kept the indexes of these ids in a treeset to lookup their index in log(n) time\nCreated a segment 
I sorted rooms according to increasing order of their id and kept the indexes of these ids in a treeset to lookup their index in log(n) time\nCreated a segment tree on rooms\' sizes which can give a range max query for room sizes on a specific range.\nFor every query, I got the closest room\'s index with id closest to the prefered id by using treeset. Then binary search on left and right of that index for prefered size. On every step on binary search I had to query the segment tree for that range\'s maxsize.\nAfter both binary search I took the best of the right and left.\n\n# **Complexity**\nAssume number of rooms is n\nand number of queries is q\n\n**Preprocessing complexity:** n*log*(n)\n**Query Complexity:** q*log*<sup>2</sup>(n)    -> (*log*<sup>2</sup>(n) for each query)\n<br>\n**Total Complexity:** <h4>n*log*(n) + q*log*<sup>2</sup>(n)</h4>\n\n# **Code**\n```\nclass Solution {\n    public int[] closestRoom(int[][] rooms, int[][] queries) {\n        int n = rooms.length;\n        int[] ids = new int[n];\n        Arrays.sort(rooms, new Comparator<int[]>() {\n            public int compare(int[] a, int[] b) {\n                return Integer.compare(a[0],b[0]);\n            }\n        });\n        int[] sizes = new int[n];\n        TreeMap<Integer,Integer> map = new TreeMap();\n        for(int i = 0; i < n; i++) {\n            int id = rooms[i][0];\n            int size = rooms[i][1];\n            ids[i] = id;\n            sizes[i] = size;\n        }\n        for(int i = 0; i < n; i++) {\n            map.put(ids[i],i);\n        }\n        int[] ans = new int[queries.length];\n        SegMax segmax = new SegMax(0,n-1,sizes);\n        for(int qq = 0; qq < queries.length; qq++) {\n            int pid = queries[qq][0];\n            Integer up = map.ceilingKey(pid);\n            Integer down = map.floorKey(pid);\n            int ppid = pid;\n            if(up==null) pid =down;\n            if(down==null) pid =up;\n            if(up!=null && down!=null) {\n                int upDiff = Math.abs(up-pid);\n                int downDiff = Math.abs(down-pid);\n                if(upDiff<downDiff) pid = up;\n                else pid = down;\n            }\n            int psize = queries[qq][1];\n            int right = map.get(pid);\n            int left = right;\n            int at = left;\n            int l = 0;\n            int r = right;\n            int leftIdx = -1;\n            int rightIdx = -1;\n            while(l<=r) {\n                int mid = (l+r)>>1;\n                int nowMax = segmax.query(mid,right);\n                if(nowMax>=psize) {\n                    leftIdx = mid;\n                    l = mid+1;\n                } else {\n                    r = mid-1;\n                }\n            }\n            l = left;\n            r = n-1;\n            while(l<=r) {\n                int mid = (l+r)>>1;\n                int nowMax = segmax.query(left,mid);\n                if(nowMax>=psize) {\n                    rightIdx = mid;\n                    r = mid-1;\n                } else {\n                    l = mid+1;\n                }\n            }\n            pid = ppid;\n            if(leftIdx!=-1 && rightIdx!=-1) {\n                int leftAns = ids[leftIdx];\n                int rightAns = ids[rightIdx];\n                int leftAbs = Math.abs(pid-leftAns);\n                int rightAbs = Math.abs(pid-rightAns);\n                if(leftAbs==rightAbs) ans[qq] = leftAns;\n                else if(leftAbs<rightAbs) ans[qq] = leftAns;\n                else ans[qq] = rightAns;\n            } else if(leftIdx!=-1) {\n                ans[qq] = ids[leftIdx];\n            } else if(rightIdx!=-1) {\n                ans[qq] = ids[rightIdx];\n            } else {\n                ans[qq] = -1;\n            }\n        \n        }\n        return ans;\n    }\n}\n\nclass SegMax {\n    int leftMost, rightMost, mid;\n    boolean leaf;\n    int max;\n    SegMax lchild, rchild;\n    \n    SegMax(int l, int r, int[] arr) {\n        leftMost = l;\n        rightMost = r;\n        mid = (l+r)>>1;\n        leaf = l==r;\n        if(leaf) max =arr[l];\n        else {\n            lchild = new SegMax(l,mid,arr);\n            rchild = new SegMax(mid+1,r,arr);\n            max = Math.max(lchild.max,rchild.max);\n        }\n    }\n    \n    int query(int l, int r) {\n        if(l>rightMost || r<leftMost) return Integer.MIN_VALUE;\n        if(l<=leftMost && rightMost<=r) return max;\n        return Math.max(lchild.query(l,r),rchild.query(l,r));\n    }\n}\n\n```
[]