2-D Binary Search
Approach: \n1. Since room has to have a size of atleast minSize from query -> Sort the queries in decreasing order of room-size {3,2,1} => This will ensure that
Approach: \n1. Since room has to have a size of atleast minSize from query -> Sort the queries in decreasing order of room-size {3,2,1} => This will ensure that if **x rooms have size atleast 3**, then `rooms having size atleast 2= x + (rooms with size2)` OR rooms with size 1= x + (rooms>1) after it in the loop. \n2. Now, we will also need the rooms size to be sorted in decreasing order to make-1 work. \nFor eg: \nLet\'s maintain a counter for where we are at in Rooms, say ptr:\n*For, QuerySize=7*\nRoomSizes: [4,3,2]\nQuerySizes:[7,3,1]\nat the start. \n\n=>When we look for rooms with size atleast 7, we will get no element\n\n*For, QuerySize=3*\n\n=>When we look for rooms with size atleast 3, we will get {4, 3} [ptr moves to idx=2]\n\n*For, QuerySize=1*\n=>When we look for rooms with size atleast 1, we will get *{4,3,2} OR {} + {4,3} + {2}* [ptr moves to end]\n\n\t3. Rest, we just need to efficiently store the possibleRoomIDs in a set and then perform binary search to get the minimum difference. \n\t4. **Case of a Tie:** We don\'t need to run a loop for this, as Tie can only be between two elements not more as RoomIDs are unique!\n\n**Time-Complexity: O(K*log(N)+N*log(N))**\n```\nclass Solution {\npublic:\n    \n    static bool mysort(vector<int>&a, vector<int>&b){\n        \n        if(a[1]==b[1])\n        {\n            return a[0]>b[0];\n        }\n        return a[1]>b[1];\n    }\n    \n    vector<int> closestRoom(vector<vector<int>>& rooms, vector<vector<int>>& queries) {\n        \n        int k= queries.size();\n        for(int i=0;i<k;i++)\n        {\n            queries[i].push_back(i);\n        }\n        \n        sort(rooms.begin(), rooms.end(), mysort);\n        sort(queries.begin(), queries.end(), mysort);\n    \n        set<int> PossibleIDs;\n        int n = rooms.size();\n        int prev=0;\n        vector<int> ans(k, -1);\n        \n        for(int i=0;i<k;i++)\n        {\n            int size_query= queries[i][1];\n            int pref_query= queries[i][0];\n            \n            while(prev<n && rooms[prev][1]>=size_query)\n            {\n                PossibleIDs.insert(rooms[prev][0]);\n                prev++;\n                \n            }\n            \n            if(PossibleIDs.size()>0)\n            {\n                auto it= PossibleIDs.lower_bound(pref_query);\n                \n                int curr_ans= (it==PossibleIDs.end())?(int)1e8:(abs(pref_query-*it));\n                int ans_push= (it==PossibleIDs.end())?(int)1e8:(*it);\n                \n                if(it!=PossibleIDs.begin())\n                {\n                    it--;  //Resolving Ties: If there is a Tie, then there can only be two cases (Upper Lower type), for eg: cur=4, arr[2,6]\n                    if(abs(pref_query-*it)<=curr_ans)\n                    {\n                        curr_ans= (pref_query-*it);\n                        ans_push= *it;\n                    }\n                }\n                ans[queries[i][2]]= (curr_ans==(int)1e8)?-1:ans_push;\n                \n            }\n            \n        }\n        return ans;\n    }\n};\n```
['C', 'Binary Tree']