Segment Tree + Binary search || Simple & Easy C++
Intuition\nIt\'s simple binary search multiple times along with the use of segment tree to find maximum in ranges efficiently. \n\n# Approach\nSorted arrays acc
# Intuition\nIt\'s simple binary search multiple times along with the use of segment tree to find maximum in ranges efficiently. \n\n# Approach\nSorted arrays according to the indices of rooms.\nI binary searched for each distance d from 0 to 1e8, and then i checked if\nthe maximum in range from i1 to i2 is >= desired size or not. I also calculated i1 and i2 using binary search. \nHere i1 = first index where **id >= desired id - d** and i2 = last index where **id <= desired id + d.** hence we get the range [i1,i2].\n\n# Complexity\n- Time complexity:\nq.log(1e8).log(n).log(n) ~ O(Q*(logn)^3)\n\n- Space complexity:\n)(4*n + n + n) ~ O(n)\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    vector<int>sgt;\n    void build(int l, int r, vector<vector<int>>& v,int node){\n        if(l==r){\n            sgt[node] = v[l][1]; return;\n        }\n        int m = l + (r-l)/2;\n        build(l,m,v,2*node); build(m+1,r,v,2*node+1);\n        sgt[node] = max(sgt[2*node],sgt[2*node+1]);\n    }\n    int find(int l, int r, int i, int j, int node){\n        if(l>=i&&r<=j) return sgt[node];\n        if(l>j||r<i) return -1;\n        int m = l + (r-l)/2;\n        return max(find(l,m,i,j,2*node),find(m+1,r,i,j,2*node+1));\n    }\n    vector<int> closestRoom(vector<vector<int>>& v, vector<vector<int>>& q) {\n        ios::sync_with_stdio(0); cin.tie(0);\n        int n = v.size();\n        sort(v.begin(),v.end());\n        map<int,int>mp;  // map just to format the output int the end\n        for(int i=0;i<n;i++) mp[v[i][0]] = v[i][1];\n        sgt.resize(4*n);\n        build(0,n-1,v,1); // classic max segment tree\n        vector<int>tmp(n); // extra temp array just to use inbuilt lb/ub\n        for(int i=0;i<n;i++) tmp[i] = v[i][0]; \n        vector<int>res(q.size(),-1); // result\n        for(int i=0;i<q.size();i++){\n            int j = q[i][0], sz = q[i][1]; int val = -1;\n            int l = 0, r = 1e8;\n            while(l<=r){\n                int m = l + (r-l)/2;\n                int i1 = lower_bound(tmp.begin(),tmp.end(),j-m) - tmp.begin();\n                int i2 = upper_bound(tmp.begin(),tmp.end(),j+m) - tmp.begin(); i2--;\n                if(i2<0||i1>i2){\n                    l=m+1; continue;\n                }\n                else if(i1==n){\n                    r=m-1; continue;\n                }\n                if(find(0,n-1,i1,i2,1)>=sz){\n                    val = m; r=m-1;\n                }\n                else l = m+1; \n            }\n            res[i] = val;\n        }\n        for(int i=0;i<q.size();i++){\n            if(res[i]==-1) continue;\n            int i1 = q[i][0] - res[i], i2 = q[i][0] + res[i];\n            if(mp[i1]>=q[i][1]) res[i] = i1; \n            else res[i] = i2;\n        }\n        return res;\n    }\n};\n```
['Binary Search', 'Segment Tree', 'C++']