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 arrayanswer of lengthk whereanswer[j]contains the answer to thejth query.

Examples

Example 1

1
2
3
4
5
6

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

1
2
3
4
5
6

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

Method 1 – Offline Query Processing with Ordered Set

Intuition

Sort the rooms by size (descending) and the queries by minSize (descending). As we process each query, we maintain a set of room IDs with sufficient size, allowing us to efficiently find the closest room ID to the preferred value using binary search.

Approach

  1. Sort rooms by size descending.
  2. For each query, keep its original index and sort queries by minSize descending.
  3. Use a balanced BST (e.g., TreeSet in Java, std::set in C++, bisect in Python) to maintain room IDs with size ≥ minSize as we process queries.
  4. For each query, use binary search to find the closest room ID to preferred. If tie, choose the smaller ID.
  5. Restore the original order of answers.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution {
public:
    vector<int> closestRoom(vector<vector<int>>& rooms, vector<vector<int>>& queries) {
        int k = queries.size();
        vector<tuple<int, int, int>> qs;
        for (int i = 0; i < k; ++i) qs.emplace_back(queries[i][1], queries[i][0], i);
        sort(rooms.begin(), rooms.end(), [](auto& a, auto& b) { return a[1] > b[1]; });
        sort(qs.begin(), qs.end(), greater<>());
        set<int> ids;
        vector<int> ans(k, -1);
        int j = 0;
        for (auto& [minSize, pref, idx] : qs) {
            while (j < rooms.size() && rooms[j][1] >= minSize) ids.insert(rooms[j++][0]);
            if (ids.empty()) continue;
            auto it = ids.lower_bound(pref);
            int res = -1, diff = INT_MAX;
            if (it != ids.end() && abs(*it - pref) < diff) { res = *it; diff = abs(*it - pref); }
            if (it != ids.begin()) {
                --it;
                if (abs(*it - pref) < diff || (abs(*it - pref) == diff && *it < res)) res = *it;
            }
            ans[idx] = res;
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

func closestRoom(rooms [][]int, queries [][]int) []int {
    type qinfo struct{ minSize, pref, idx int }
    k := len(queries)
    qs := make([]qinfo, k)
    for i, q := range queries {
        qs[i] = qinfo{q[1], q[0], i}
    }
    sort.Slice(rooms, func(i, j int) bool { return rooms[i][1] > rooms[j][1] })
    sort.Slice(qs, func(i, j int) bool { return qs[i].minSize > qs[j].minSize })
    ids := []int{}
    ans := make([]int, k)
    for i := range ans { ans[i] = -1 }
    j := 0
    for _, q := range qs {
        for j < len(rooms) && rooms[j][1] >= q.minSize {
            ids = append(ids, rooms[j][0])
            j++
        }
        if len(ids) == 0 { continue }
        sort.Ints(ids)
        idx := sort.SearchInts(ids, q.pref)
        res, diff := -1, 1<<31-1
        if idx < len(ids) && abs(ids[idx]-q.pref) < diff {
            res, diff = ids[idx], abs(ids[idx]-q.pref)
        }
        if idx > 0 && (abs(ids[idx-1]-q.pref) < diff || (abs(ids[idx-1]-q.pref) == diff && ids[idx-1] < res)) {
            res = ids[idx-1]
        }
        ans[q.idx] = res
    }
    return ans
}
func abs(x int) int { if x < 0 { return -x }; return x }
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

class Solution {
    public int[] closestRoom(int[][] rooms, int[][] queries) {
        int k = queries.length;
        int[][] qs = new int[k][3];
        for (int i = 0; i < k; i++) {
            qs[i][0] = queries[i][1];
            qs[i][1] = queries[i][0];
            qs[i][2] = i;
        }
        Arrays.sort(rooms, (a, b) -> b[1] - a[1]);
        Arrays.sort(qs, (a, b) -> b[0] - a[0]);
        TreeSet<Integer> ids = new TreeSet<>();
        int[] ans = new int[k];
        Arrays.fill(ans, -1);
        int j = 0;
        for (int[] q : qs) {
            while (j < rooms.length && rooms[j][1] >= q[0]) ids.add(rooms[j++][0]);
            if (ids.isEmpty()) continue;
            Integer hi = ids.ceiling(q[1]), lo = ids.floor(q[1]);
            int res = -1, diff = Integer.MAX_VALUE;
            if (hi != null && Math.abs(hi - q[1]) < diff) { res = hi; diff = Math.abs(hi - q[1]); }
            if (lo != null && (Math.abs(lo - q[1]) < diff || (Math.abs(lo - q[1]) == diff && lo < res))) res = lo;
            ans[q[2]] = res;
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
    fun closestRoom(rooms: Array<IntArray>, queries: Array<IntArray>): IntArray {
        val k = queries.size
        val qs = Array(k) { intArrayOf(queries[it][1], queries[it][0], it) }
        rooms.sortByDescending { it[1] }
        qs.sortByDescending { it[0] }
        val ids = sortedSetOf<Int>()
        val ans = IntArray(k) { -1 }
        var j = 0
        for (q in qs) {
            while (j < rooms.size && rooms[j][1] >= q[0]) ids.add(rooms[j++][0])
            if (ids.isEmpty()) continue
            val hi = ids.ceiling(q[1])
            val lo = ids.floor(q[1])
            var res = -1; var diff = Int.MAX_VALUE
            if (hi != null && kotlin.math.abs(hi - q[1]) < diff) { res = hi; diff = kotlin.math.abs(hi - q[1]) }
            if (lo != null && (kotlin.math.abs(lo - q[1]) < diff || (kotlin.math.abs(lo - q[1]) == diff && lo < res))) res = lo
            ans[q[2]] = res
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution:
    def closestRoom(self, rooms: list[list[int]], queries: list[list[int]]) -> list[int]:
        from bisect import bisect_left
        rooms.sort(key=lambda x: -x[1])
        qs = sorted([(minSize, pref, i) for i, (pref, minSize) in enumerate(queries)], reverse=True)
        ans = [-1] * len(queries)
        ids = []
        j = 0
        for minSize, pref, idx in qs:
            while j < len(rooms) and rooms[j][1] >= minSize:
                bisect.insort(ids, rooms[j][0])
                j += 1
            if not ids:
                continue
            i = bisect_left(ids, pref)
            res, diff = -1, float('inf')
            if i < len(ids) and abs(ids[i] - pref) < diff:
                res, diff = ids[i], abs(ids[i] - pref)
            if i > 0 and (abs(ids[i-1] - pref) < diff or (abs(ids[i-1] - pref) == diff and ids[i-1] < res)):
                res = ids[i-1]
            ans[idx] = res
        return ans

Complexity

  • ⏰ Time complexity: O((n + k) log n)
  • 🧺 Space complexity: O(n + k)