Formatted question description: https://leetcode.ca/all/1847.html

# 1847. Closest Room

## Level

Hard

## Description

There is a hotel with `n`

rooms. The rooms are represented by a 2D integer array `rooms`

where `rooms[i] = [roomId_i, size_i]`

denotes that there is a room with room number `roomId_i`

and size equal to `size_i`

. Each `roomId_i`

is guaranteed to be **unique**.

You are also given `k`

queries in a 2D array `queries`

where `queries[j] = [preferred_j, minSize_j]`

. The answer to the `j-th`

query is the room number `id`

of a room such that:

- The room has a size of
**at least**`minSize_j`

, and `abs(id - preferred_j)`

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 j-th 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 <= roomId_i, preferred_j <= 10^7`

`1 <= size_i, minSize_j <= 10^7`

## Solution

Sort `rooms`

according to sizes in decreasing order. Sort `queries`

according to `minSize`

s in decreasing order, and store the queries’ indices in the original `queries`

.

Use a tree set to store the room numbers. Loop over the sorted queries. For each query, loop over the sorted `rooms`

and add all the rooms that have sizes greater than or equal to the current query’s `minSize`

to the tree set. Then use `preferred`

to find the two closest room numbers in the tree set, which are `floor`

and `ceiling`

. If neither `floor`

nor `ceiling`

exists, the query result is -1. If only one of `floor`

and `ceiling`

exists, the query result is the one that exists. If both `floor`

and `ceiling`

exist, then calculate the differences and the query result is the one with the minimum difference.

```
class Solution {
public int[] closestRoom(int[][] rooms, int[][] queries) {
int roomsCount = rooms.length;
int queriesCount = queries.length;
Arrays.sort(rooms, new Comparator<int[]>() {
public int compare(int[] room1, int[] room2) {
return room2[1] - room1[1];
}
});
int[][] newQueries = new int[queriesCount][3];
for (int i = 0; i < queriesCount; i++) {
newQueries[i][0] = queries[i][0];
newQueries[i][1] = queries[i][1];
newQueries[i][2] = i;
}
Arrays.sort(newQueries, new Comparator<int[]>() {
public int compare(int[] query1, int[] query2) {
return query2[1] - query1[1];
}
});
TreeSet<Integer> set = new TreeSet<Integer>();
int roomIndex = 0;
int[] answer = new int[queriesCount];
for (int i = 0; i < queriesCount; i++) {
int[] query = newQueries[i];
int preferred = query[0], minSize = query[1], index = query[2];
while (roomIndex < roomsCount && rooms[roomIndex][1] >= minSize) {
set.add(rooms[roomIndex][0]);
roomIndex++;
}
Integer floor = set.floor(preferred), ceiling = set.ceiling(preferred);
if (floor == null && ceiling == null)
answer[index] = -1;
else if (floor == null)
answer[index] = ceiling;
else if (ceiling == null)
answer[index] = floor;
else {
int difference1 = preferred - floor, difference2 = ceiling - preferred;
if (difference1 <= difference2)
answer[index] = floor;
else
answer[index] = ceiling;
}
}
return answer;
}
}
```