# Closest Room
**Difficulty:** HARD
[External](https://leetcode.com/problems/closest-room)
Canonical: https://scaleengineer.com/dsa/problems/closest-room
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search), [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array, Ordered Set
---
## Problem
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 <= 105`
* `k == queries.length`
* `1 <= k <= 104`
* `1 <= roomIdi, preferredj <= 107`
* `1 <= sizei, minSizej <= 107`

# Approaches
## Brute Force Iteration
This approach involves iterating through every room for each query. For a given query, we check every room to see if it meets the minimum size requirement. Among the valid rooms, we keep track of the one that has the minimum absolute difference in room ID compared to the preferred ID.
**Time:** O(N * K), where N is the number of rooms and K is the number of queries. For each of the K queries, we perform a linear scan of all N rooms. · **Space:** O(K) or O(1). O(K) to store the answer array. If the output array is not considered part of the space complexity, it is O(1).
**Pros:** Simple to understand and implement.; Requires minimal extra space.
**Cons:** Highly inefficient for large inputs.; Will likely result in a 'Time Limit Exceeded' (TLE) error on competitive programming platforms due to its quadratic time complexity.
### Explanation
The algorithm iterates through each of the `k` queries. For each query `[preferred_j, minSize_j]`, it initializes a variable `bestRoomId` to -1 and `minDiff` to infinity. It then iterates through all `n` rooms `[roomId_i, size_i]`. Inside the inner loop, it checks if `size_i >= minSize_j`. If the size condition is met, it calculates the absolute difference `diff = abs(roomId_i - preferred_j)`. It compares this `diff` with the current `minDiff`. If the new `diff` is smaller, the current room becomes the best candidate. If the `diff` is the same, the tie-breaking rule (smaller `roomId`) is applied. After checking all rooms, the best found room ID is the answer for the current query. This process is repeated for all queries.

```java
class Solution {
    public int[] closestRoom(int[][] rooms, int[][] queries) {
        int k = queries.length;
        int[] ans = new int[k];

        for (int j = 0; j < k; j++) {
            int preferred = queries[j][0];
            int minSize = queries[j][1];
            
            int bestRoomId = -1;
            int minDiff = Integer.MAX_VALUE;

            for (int[] room : rooms) {
                int roomId = room[0];
                int size = room[1];

                if (size >= minSize) {
                    int diff = Math.abs(roomId - preferred);
                    if (diff < minDiff) {
                        minDiff = diff;
                        bestRoomId = roomId;
                    } else if (diff == minDiff) {
                        bestRoomId = Math.min(bestRoomId, roomId);
                    }
                }
            }
            ans[j] = bestRoomId;
        }
        return ans;
    }
}
```
### Algorithm
1. Initialize an answer array `ans` of size `k`.
2. Iterate through each query `j` from `0` to `k-1`.
3. For each query `[preferred_j, minSize_j]`, initialize `bestRoomId = -1` and `minDiff = infinity`.
4. Iterate through each room `i` from `0` to `n-1`.
5. Let the current room be `[roomId_i, size_i]`.
6. Check if `size_i >= minSize_j`.
7. If the condition is met, calculate the difference `diff = abs(roomId_i - preferred_j)`.
8. Compare `diff` with `minDiff`:
    - If `diff < minDiff`, update `minDiff = diff` and `bestRoomId = roomId_i`.
    - If `diff == minDiff`, update `bestRoomId = min(bestRoomId, roomId_i)` to handle the tie-breaking rule.
9. After iterating through all rooms, store the final `bestRoomId` in `ans[j]`.
10. After iterating through all queries, return the `ans` array.

## Offline Processing with Sorting and TreeSet
This is a much more efficient approach that avoids re-evaluating rooms for every query. The core idea is to process queries "offline". We sort both the rooms and the queries based on size in descending order. This allows us to consider rooms in a way that once a room is available for a high `minSize` query, it remains available for all subsequent (lower `minSize`) queries. We use a `TreeSet` to maintain the IDs of available rooms, which allows for efficient searching of the closest ID.
**Time:** O(N log N + K log K). Sorting rooms takes O(N log N) and sorting queries takes O(K log K). The main processing loop involves O(N) insertions into the `TreeSet` (each O(log N)) and O(K) lookups (each O(log N)). The total time is dominated by the initial sorting steps, resulting in O(N log N + K log K). · **Space:** O(N + K). We need O(K) space for the augmented queries array and the answer array. The `TreeSet` can store up to N room IDs in the worst case, requiring O(N) space.
**Pros:** Highly efficient and passes the given constraints.; The offline processing technique is a powerful and generalizable pattern for similar problems.
**Cons:** More complex to implement compared to the brute-force approach.; Requires modifying the query structure and careful handling of pointers and data structures.
### Explanation
This optimized approach hinges on processing queries offline. First, we sort the rooms by size in descending order. We also augment the queries to include their original index and then sort them by their `minSize` requirement, also in descending order. This sorting strategy is key: as we process queries with decreasing `minSize`, the set of available rooms only grows. 

We iterate through the sorted queries. For each query, we add all rooms that now meet the `minSize` requirement into a `TreeSet`. A `TreeSet` is a balanced binary search tree that stores elements in sorted order and allows for efficient lookups. Since both rooms and queries are sorted by size, we can do this with a single pass over the rooms array across all queries. 

Once the `TreeSet` contains all valid room IDs for the current query, we find the closest ID to the `preferred` ID. The two potential candidates are the `floor` (largest ID <= preferred) and `ceiling` (smallest ID >= preferred). We compare these two candidates, find the one with the minimum absolute difference, handle the tie-breaking rule, and store the result in an answer array at its original index. This avoids the O(N) scan for each query, leading to a much better time complexity.

```java
import java.util.Arrays;
import java.util.TreeSet;

class Solution {
    public int[] closestRoom(int[][] rooms, int[][] queries) {
        int n = rooms.length;
        int k = queries.length;

        // Sort rooms by size in descending order
        Arrays.sort(rooms, (a, b) -> Integer.compare(b[1], a[1]));

        // Augment queries with original index
        int[][] indexedQueries = new int[k][3];
        for (int i = 0; i < k; i++) {
            indexedQueries[i][0] = queries[i][0]; // preferred
            indexedQueries[i][1] = queries[i][1]; // minSize
            indexedQueries[i][2] = i;             // original index
        }

        // Sort queries by minSize in descending order
        Arrays.sort(indexedQueries, (a, b) -> Integer.compare(b[1], a[1]));

        int[] ans = new int[k];
        TreeSet<Integer> availableRoomIds = new TreeSet<>();
        int roomIndex = 0;

        for (int[] query : indexedQueries) {
            int preferred = query[0];
            int minSize = query[1];
            int originalIndex = query[2];

            // Add all rooms with size >= minSize to the TreeSet
            while (roomIndex < n && rooms[roomIndex][1] >= minSize) {
                availableRoomIds.add(rooms[roomIndex][0]);
                roomIndex++;
            }

            // Find the closest room ID from the available ones
            if (availableRoomIds.isEmpty()) {
                ans[originalIndex] = -1;
                continue;
            }

            Integer floor = availableRoomIds.floor(preferred);
            Integer ceil = availableRoomIds.ceiling(preferred);

            int bestRoomId = -1;
            int minDiff = Integer.MAX_VALUE;

            if (floor != null) {
                int diff = preferred - floor;
                if (diff < minDiff) {
                    minDiff = diff;
                    bestRoomId = floor;
                }
            }

            if (ceil != null) {
                int diff = ceil - preferred;
                if (diff < minDiff) {
                    minDiff = diff;
                    bestRoomId = ceil;
                } else if (diff == minDiff) {
                    bestRoomId = Math.min(bestRoomId, ceil);
                }
            }
            
            ans[originalIndex] = bestRoomId;
        }

        return ans;
    }
}
```
### Algorithm
1. **Preprocessing:**
    - Augment the `queries` array to store the original index of each query: `[preferred, minSize, original_index]`.
    - Sort the `rooms` array in descending order of `size`.
    - Sort the augmented `queries` array in descending order of `minSize`.
2. **Processing:**
    - Initialize an empty `TreeSet<Integer>` named `availableRoomIds` to store IDs of rooms that meet the size criteria.
    - Initialize an answer array `ans` of size `k`.
    - Initialize a pointer `roomIndex = 0` for the sorted `rooms` array.
3. **Iterate through sorted queries:**
    - For each query `[preferred, minSize, originalIndex]`:
        a. Add newly available rooms: While `roomIndex < n` and `rooms[roomIndex][1] >= minSize`, add `rooms[roomIndex][0]` to `availableRoomIds` and increment `roomIndex`.
        b. Find the closest room ID in `availableRoomIds`:
            - If `availableRoomIds` is empty, the answer is -1.
            - Otherwise, find the two best candidates using `floor(preferred)` and `ceiling(preferred)` methods of the `TreeSet`.
            - Compare these two candidates to find the one with the minimum absolute difference from `preferred`, respecting the tie-breaking rule (smaller ID).
        c. Store the result in `ans[originalIndex]`.
4. **Return `ans`**.

# Solutions
### Java

```java
class Solution { public int [] closestRoom ( int [][] rooms , int [][] queries ) { int n = rooms . length ; int k = queries . length ; Arrays . sort ( rooms , ( a , b ) -> a [ 1 ] - b [ 1 ]); Integer [] idx = new Integer [ k ]; for ( int i = 0 ; i < k ; i ++) { idx [ i ] = i ; } Arrays . sort ( idx , ( i , j ) -> queries [ i ][ 1 ] - queries [ j ][ 1 ]); int i = 0 ; TreeMap < Integer , Integer > tm = new TreeMap <>(); for ( int [] room : rooms ) { tm . merge ( room [ 0 ], 1 , Integer: : sum ); } int [] ans = new int [ k ]; Arrays . fill ( ans , - 1 ); for ( int j : idx ) { int prefer = queries [ j ][ 0 ], minSize = queries [ j ][ 1 ]; while ( i < n && rooms [ i ][ 1 ] < minSize ) { if ( tm . merge ( rooms [ i ][ 0 ], - 1 , Integer: : sum ) == 0 ) { tm . remove ( rooms [ i ][ 0 ]); } ++ i ; } if ( i == n ) { break ; } Integer p = tm . ceilingKey ( prefer ); if ( p != null ) { ans [ j ] = p ; } p = tm . floorKey ( prefer ); if ( p != null && ( ans [ j ] == - 1 || ans [ j ] - prefer >= prefer - p )) { ans [ j ] = p ; } } return ans ; } }
```

### CPP

```cpp
class Solution { public: vector < int > closestRoom ( vector < vector < int >>& rooms , vector < vector < int >>& queries ) { int n = rooms . size (); int k = queries . size (); sort ( rooms . begin (), rooms . end (), []( const vector < int >& a , const vector < int >& b ) { return a [ 1 ] < b [ 1 ]; }); vector < int > idx ( k ); iota ( idx . begin (), idx . end (), 0 ); sort ( idx . begin (), idx . end (), [ & ]( int i , int j ) { return queries [ i ][ 1 ] < queries [ j ][ 1 ]; }); vector < int > ans ( k , - 1 ); int i = 0 ; multiset < int > s ; for ( auto & room : rooms ) { s . insert ( room [ 0 ]); } for ( int j : idx ) { int prefer = queries [ j ][ 0 ], minSize = queries [ j ][ 1 ]; while ( i < n && rooms [ i ][ 1 ] < minSize ) { s . erase ( s . find ( rooms [ i ][ 0 ])); ++ i ; } if ( i == n ) { break ; } auto it = s . lower_bound ( prefer ); if ( it != s . end ()) { ans [ j ] = * it ; } if ( it != s . begin ()) { -- it ; if ( ans [ j ] == - 1 || abs ( * it - prefer ) <= abs ( ans [ j ] - prefer )) { ans [ j ] = * it ; } } } return ans ; } };
```

### Python

```python
from sortedcontainers import SortedList class Solution : def closestRoom ( self , rooms : List [ List [ int ]], queries : List [ List [ int ]] ) -> List [ int ]: rooms . sort ( key = lambda x : x [ 1 ]) k = len ( queries ) idx = sorted ( range ( k ), key = lambda i : queries [ i ][ 1 ]) ans = [ - 1 ] * k i , n = 0 , len ( rooms ) sl = SortedList ( x [ 0 ] for x in rooms ) for j in idx : prefer , minSize = queries [ j ] while i < n and rooms [ i ][ 1 ] < minSize : sl . remove ( rooms [ i ][ 0 ]) i += 1 if i == n : break p = sl . bisect_left ( prefer ) if p < len ( sl ): ans [ j ] = sl [ p ] if p and ( ans [ j ] == - 1 or ans [ j ] - prefer >= prefer - sl [ p - 1 ]): ans [ j ] = sl [ p - 1 ] return ans
```