# LeetCode 1847. Closest Room

There is a hotel with `n` rooms. The rooms are represented by a 2D integer array `rooms` where `rooms[i] = [roomIdi, sizei]` denotes that there is a room with room number `roomIdi` and size equal to `sizei`. Each `roomIdi` is guaranteed to be **unique**.

You are also given `k` queries in a 2D array `queries` where `queries[j] = [preferredj, minSizej]`. The answer to the `jth` query is the room number `id` of a room such that:

* The room has a size of **at least** `minSizej`, and
* `abs(id - preferredj)` is **minimized**, where `abs(x)` is the absolute value of `x`.

If there is a **tie** in the absolute difference, then use the room with the **smallest** such `id`. If there is **no such room**, the answer is `-1`.

Return *an array* `answer` *of length* `k` *where* `answer[j]` *contains the answer to the* `jth` *query*.

**Example 1:**

```
Input: rooms = [[2,2],[1,2],[3,2]], queries = [[3,1],[3,3],[5,2]]
Output: [3,-1,3]
Explanation: The answers to the queries are as follows:
Query = [3,1]: Room number 3 is the closest as abs(3 - 3) = 0, and its size of 2 is at least 1. The answer is 3.
Query = [3,3]: There are no rooms with a size of at least 3, so the answer is -1.
Query = [5,2]: Room number 3 is the closest as abs(3 - 5) = 2, and its size of 2 is at least 2. The answer is 3.
```

**Example 2:**

```
Input: rooms = [[1,4],[2,3],[3,5],[4,1],[5,2]], queries = [[2,3],[2,4],[2,5]]
Output: [2,1,3]
Explanation: The answers to the queries are as follows:
Query = [2,3]: Room number 2 is the closest as abs(2 - 2) = 0, and its size of 3 is at least 3. The answer is 2.
Query = [2,4]: Room numbers 1 and 3 both have sizes of at least 4. The answer is 1 since it is smaller.
Query = [2,5]: Room number 3 is the only room with a size of at least 5. The answer is 3.
```

**Constraints:**

* `n == rooms.length`
* `1 <= n <= 10^5`
* `k == queries.length`
* `1 <= k <= 10^4`
* `1 <= roomIdi, preferredj <= 10^7`
* `1 <= sizei, minSizej <= 10^7`

## Solution

[English Version in Youtube](https://youtu.be/Q1WGr7fxA6g)

[中文版解答Youtube Link](https://youtu.be/6QW31b5CeoQ)

[中文版解答Bilibili Link](https://www.bilibili.com/video/BV13B4y1w7wS/)

```
class Solution {
public:
    vector<int> closestRoom(vector<vector<int>>& rooms, vector<vector<int>>& queries) {
        int m = queries.size();
        vector<int> idx(m);
        std::iota(idx.begin(), idx.end(), 0);

        std::sort(idx.begin(), idx.end(), [&queries](int idx1, int idx2) {
            return queries[idx1][1] > queries[idx2][1];
        });
        std::sort(rooms.begin(), rooms.end(), [](const vector<int>& room1, const vector<int>& room2) {
            return room1[1] > room2[1];
        });
        
        vector<int> ans(m, -1);
        int room_idx = 0;
        set<int> valid_rooms;
        for (int e : idx) {
            int preferred = queries[e][0];
            int min_size = queries[e][1];
            
            while (room_idx < rooms.size() && rooms[room_idx][1] >= min_size) {
                valid_rooms.insert(rooms[room_idx][0]);
                room_idx++;
            }
            
            if (valid_rooms.empty()) {
                continue;
            }
            
            auto it = valid_rooms.upper_bound(preferred);
            if (it != valid_rooms.end()) {
                ans[e] = *it;
            }
            if (it != valid_rooms.begin()) {
                it--;
                if (ans[e] == -1) {
                    ans[e] = *it;
                } else if (preferred - *it <= ans[e] - preferred) {
                    ans[e] = *it;
                }
            }
        }
        
        return ans;
    }
};
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://zhenchaogan.gitbook.io/leetcode-solution/leetcode-1847-closest-room.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.