Sorting + Binary Search + Offline Queries
Complexity\n- Time complexity: O(nlog(n) + klog(k) + k*log(n))\n- Space complexity: O(n)\n\n# Code\n\nclass Solution {\npublic:\n    vector<int> closestRoom(vec
# Complexity\n- Time complexity: $$O(n*log(n) + k*log(k) + k*log(n))$$\n- Space complexity: $$O(n)$$\n\n# Code\n```\nclass Solution {\npublic:\n    vector<int> closestRoom(vector<vector<int>>& rooms, vector<vector<int>>& queries) {\n        // add all the room IDs to a set\n        set<int> availableRooms;\n\n        for(vector<int>& room : rooms) {\n            availableRooms.insert(room[0]);\n        }\n\n        // sort the rooms in increasing order of size\n        sort(rooms.begin(), rooms.end(), [](vector<int>& a, vector<int>& b) {\n            return a[1] < b[1];\n        });\n\n        // add index to each query\n        for(int i=0; i<queries.size(); i++) {\n            queries[i].push_back(i);\n        }\n\n        // sort the queries in increasing order of size\n        sort(queries.begin(), queries.end(), [](vector<int>& a, vector<int>& b) {\n            return a[1] < b[1];\n        });\n\n        vector<int> answer(queries.size());\n        int i = 0;\n\n        // now process each query\n        for(vector<int>& q : queries) {\n            int pref = q[0];\n            int minsize = q[1];\n\n            // remove the rooms with size less than minsize\n            while(i<rooms.size() and rooms[i][1]<minsize) {\n                // remove the room from available rooms\n                availableRooms.erase(rooms[i][0]);\n                i++;\n            }\n\n            // do lower bound binary search to find the\n            // value closest to pref\n            set<int> :: iterator it = availableRooms.lower_bound(pref);\n\n            int diff = INT_MAX;\n            int roomID = -1;\n\n            if(it != availableRooms.end()) {\n                diff = *it - pref;\n                roomID = *it;\n            }\n\n            if(it != availableRooms.begin()) {\n                if(diff >= (pref - *prev(it))) {\n                    roomID = *prev(it);\n                }\n            }\n\n            answer[q[2]] = roomID;\n        }\n\n        return answer;\n    }\n};\n```
['Binary Search', 'Sorting', 'C++']