C++/Java Sort Queries
Our per-query time complexity should be better than O(n), so we will shoot for O(log n).\n\nTo do that, we need to binary search for our room in a list of rooms
Our per-query time complexity should be better than O(n), so we will shoot for O(log n).\n\nTo do that, we need to binary search for our room in a list of rooms sorted by `id`. However, all rooms in that list should have an acceptable size.  If we process our queries based on the room size, from largest to smallest, we can efficiently track the list of acceptable rooms.\n\nWe first sort our rooms and queries by the room size in the decreasing order. Then, for each query, we add acceptable rooms into a set (`ids`). We only process each room once, as our iterator (`it`) points to the largest room that is not yet in a set.\n\nFinally, we binary-search for the closest id.\n\n**C++**\n```cpp\nvector<int> closestRoom(vector<vector<int>>& rooms, vector<vector<int>>& qs) {\n    auto by_size_desc = [](const auto& a, const auto& b) { return a[1] > b[1]; };\n    vector<int> res(qs.size());\n    for (int i = 0; i < qs.size(); ++i)\n        qs[i].push_back(i);\n    sort(begin(rooms), end(rooms), by_size_desc);    \n    sort(begin(qs), end(qs), by_size_desc);\n    set<int> ids;\n    for (int i = 0, j = 0; i < qs.size(); ++i) {\n        for (; j < rooms.size() && rooms[j][1] >= qs[i][1]; ++j)\n            ids.insert(rooms[j][0]);\n        auto it = ids.lower_bound(qs[i][0]);\n        int id1 = it == begin(ids) ? -1 : *(prev(it));\n        int id2 = it == end(ids) ? -1 : *it;\n        res[qs[i][2]] = min(id1, id2) == -1 ? max(id1, id2) : abs(qs[i][0] - id1) <= abs(qs[i][0] - id2) ? id1 : id2;\n    }\n    return res;\n}\n```\n**Java**\n```java\npublic int[] closestRoom(int[][] rooms, int[][] queries) {\n    int[] res = new int[queries.length];\n    int[][] qs = new int[queries.length][];\n    for (var i = 0; i < queries.length; ++i) \n        qs[i] = new int[] { queries[i][0], queries[i][1], i};\n    Arrays.sort(rooms, (a, b) -> b[1] - a[1]);        \n    Arrays.sort(qs, (a, b) -> b[1] - a[1]);    \n    int id = 0;\n    var ids = new TreeSet<Integer>();\n    for (var q : qs) {\n        for(; id < rooms.length && rooms[id][1] >= q[1]; ++id)\n            ids.add(rooms[id][0]);\n        Integer ans1 = ids.floor(q[0]), ans2 = ids.ceiling(q[0]);    \n        if (ans1 != null && ans2 != null)\n            res[q[2]] = q[0] - ans1 <= ans2 - q[0] ? ans1 : ans2;\n        else\n            res[q[2]] = ans1 == null && ans2 == null ? -1 : ans1 == null ? ans2 : ans1;\n    }\n    return res;\n}\n```
[]