Welcome to Subscribe On Youtube
1847. Closest Room
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, whereabs(x)
is the absolute value ofx
.
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}
Solutions
Solution 1: Offline Query + Ordered Set + Binary Search
We notice that the order of queries does not affect the answer, and the problem involves the size relationship of room areas. Therefore, we can sort the queries in ascending order of minimum area, so that we can process each query from small to large. Also, we sort the rooms in ascending order of area.
Next, we create an ordered list and add all room numbers to the ordered list.
Then, we process each query from small to large. For each query, we first remove all rooms with an area less than or equal to the current query’s minimum area from the ordered list. Then, in the remaining rooms, we use binary search to find the room number closest to the current query. If there is no such room, we return $1$.
The time complexity is $O(n \times \log n + k \times \log k)$, and the space complexity is $O(n + k)$. Where $n$ and $k$ are the number of rooms and queries, respectively.

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; } }

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; } };

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

func closestRoom(rooms [][]int, queries [][]int) []int { n, k := len(rooms), len(queries) sort.Slice(rooms, func(i, j int) bool { return rooms[i][1] < rooms[j][1] }) idx := make([]int, k) ans := make([]int, k) for i := range idx { idx[i] = i ans[i] = 1 } sort.Slice(idx, func(i, j int) bool { return queries[idx[i]][1] < queries[idx[j]][1] }) rbt := redblacktree.NewWithIntComparator() merge := func(rbt *redblacktree.Tree, key, value int) { if v, ok := rbt.Get(key); ok { nxt := v.(int) + value if nxt == 0 { rbt.Remove(key) } else { rbt.Put(key, nxt) } } else { rbt.Put(key, value) } } for _, room := range rooms { merge(rbt, room[0], 1) } i := 0 for _, j := range idx { prefer, minSize := queries[j][0], queries[j][1] for i < n && rooms[i][1] < minSize { merge(rbt, rooms[i][0], 1) i++ } if i == n { break } c, _ := rbt.Ceiling(prefer) f, _ := rbt.Floor(prefer) if c != nil { ans[j] = c.Key.(int) } if f != nil && (ans[j] == 1  ans[j]prefer >= preferf.Key.(int)) { ans[j] = f.Key.(int) } } return ans }