C++ | Segment Tree + Binary Search
I though a segment tree approach would be faster but turned out to be not true.\nTime complexity :  O(m(logn)^2 + nlogn) - for m queries and n rooms\n\n\nclass 
I though a segment tree approach would be faster but turned out to be not true.\nTime complexity :  O(m(logn)^2 + nlogn) - for m queries and n rooms\n\n```\nclass Solution {\npublic:\n    vector<int> closestRoom(vector<vector<int>>& rooms, vector<vector<int>>& queries) {\n        \n        //sort based on index\n        sort(rooms.begin(), rooms.end());\n        this->rooms = rooms;\n        \n        int length = rooms.size();\n        \n        //keep track of repeated queries\n        unordered_map<int, unordered_map<int, int>> queries_map;\n        \n        //map room_id to index and vice versa for making segment tree\n        unordered_map<int, int> room_index_id;\n        map<int, int> room_id_index;\n        for (int index = 0; index < length; index++)\n        {\n            room_index_id[index] = rooms[index][0];\n            room_id_index[rooms[index][0]] = index;\n        }\n        \n        //Construct a segment tree that can return max in a range based on index\n        constructTree(0, 0, length - 1);\n        \n        vector<int> responses;\n        \n        //repeat for each query\n        for(auto& query : queries)\n        {\n            int room_id = query[0];\n            int minSize = query[1];\n            \n            //check if it is a repeated query\n            if (queries_map.find(room_id) != queries_map.end() \n                && queries_map[room_id].find(minSize) != queries_map[room_id].end())\n            {\n                responses.push_back(queries_map[room_id][minSize]);\n                continue;\n            }\n            \n            //Binary search on the left and right\n            //Finding the right indices to search for\n            auto itr = room_id_index.upper_bound(room_id);\n            int room_index_right = -1;\n            int room_index_left  = -1;\n            if (itr == room_id_index.end())\n            {\n                itr = prev(itr);\n                room_index_left = itr->second;\n            }\n            \n            room_index_right = itr->second;\n            room_index_left = prev(itr)->second;\n            \n            //find the closes room on the right that meets the size requirement\n            int low  = room_index_right;\n            int high = length - 1;\n            int closest_right_index = -1;\n            \n            if (room_index_right != -1)\n            {\n                while(low <= high)\n                {\n                    int mid = (low + high) / 2;\n                    //each getMax takes O(logn) and we do that O(logn) times\n                    int range_maxSize = getMax(0, 0, length - 1, room_index_right, mid);\n                    if (range_maxSize >= minSize)\n                    {\n                        high = mid - 1;\n                        closest_right_index = mid;\n                    }\n                    else\n                    {\n                        low = mid + 1;\n                    }\n                }\n            }\n            \n            //find the closest room on the left that meets the size requirement\n            low  = 0;\n            high = room_index_left;\n            int closest_left_index = -1;\n            \n            while(low <= high)\n            {\n                int mid = (low + high) / 2;\n                //each getMax takes O(logn) and we do that O(logn) times\n                int range_maxSize = getMax(0, 0, length - 1, mid, room_index_left);\n                if (range_maxSize >= minSize)\n                {\n                    low = mid + 1;\n                    closest_left_index = mid;\n                }\n                else\n                {\n                    high = mid - 1;\n                }\n            }\n            \n            //find the closes\n            //map the indices back to the room_ids and find the closest one\n            int closest_left  = closest_left_index >= 0 ? room_index_id[closest_left_index] : -1;\n            int closest_right = closest_right_index >= 0 ? room_index_id[closest_right_index] : -1;\n            int response = -1;\n            \n            if (closest_left != -1 && closest_right == -1)\n            {\n                response = closest_left;\n            }\n            else if (closest_left == -1 && closest_right != -1)\n            {\n                response = closest_right;\n            }\n            else\n            {\n                if (room_id - closest_left <= closest_right - room_id)\n                {\n                    response = closest_left;\n                }\n                else\n                {\n                    response = closest_right;\n                }\n            }\n            responses.push_back(response);\n            queries_map[room_id][minSize] = response;\n        }\n        return responses;\n    }\n    \n    unordered_map<int, int> node_max;\n    vector<vector<int>> rooms;\n    \n    int constructTree(int node_index, int left, int right)\n    {\n        if (left == right)\n        {\n            return node_max[node_index] = rooms[left][1];\n        }\n        int mid = (left + right) / 2;\n        return node_max[node_index] = max(constructTree(node_index * 2 + 1, left, mid), \n                                          constructTree(node_index * 2 + 2, mid + 1, right));\n    }\n    \n    int getMax(int node_index, int node_left, int node_right, int start, int end)\n    {\n        \n        if (start <= node_left && end >= node_right)\n        {\n            return node_max[node_index];\n        }\n        if (start > node_right || end < node_left || start > end)\n        {\n            return -1;\n        }\n        int mid = (node_left + node_right) / 2;\n        return max(getMax(node_index * 2 + 1, node_left, mid, start, end), \n                   getMax(node_index * 2 + 2, mid + 1, node_right, start, end));\n    }\n                                          \n};\n```\n
[]