Welcome to Subscribe On Youtube
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 jth
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 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 <= 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; } }

// OJ: https://leetcode.com/problems/closestroom/ // Time: O(RlogR + QlogQ + QlogR) // Space: O(R) class Solution { public: vector<int> closestRoom(vector<vector<int>>& R, vector<vector<int>>& Q) { sort(begin(R), end(R), [](auto &a, auto &b) { return a[1] < b[1]; }); vector<int> ans(Q.size(), 1); for (int i = 0; i < Q.size(); ++i) Q[i].push_back(i); sort(begin(Q), end(Q), [](auto &a, auto &b) { return a[1] > b[1]; }); set<int> ids; int i = R.size()  1; for (auto &q : Q) { int pref = q[0], mn = q[1], index = q[2]; while (i >= 0 && R[i][1] >= mn) ids.insert(R[i][0]); auto it = ids.lower_bound(pref); int d1 = INT_MAX, d2 = INT_MAX; if (it != ids.end()) d2 = *it  pref; if (it != ids.begin()) d1 = pref  *prev(it); if (d1 != INT_MAX  d2 != INT_MAX) ans[index] = d1 <= d2 ? *prev(it) : *it; } return ans; } };

# 1847. Closest Room # https://leetcode.com/problems/closestroom from sortedcontainers import SortedList class Solution: def closestRoom(self, rooms, queries): Q = sorted([(y, x, i) for i, (x,y) in enumerate(queries)])[::1] R = sorted((y, x) for x, y in rooms)[::1] n, q = len(R), len(Q) p1, p2, aval, ans = 0, 0, SortedList(), [1]*q while p1 <= n and p2 < q: if p1 < n and R[p1][0] >= Q[p2][0]: aval.add(R[p1][1]) p1 += 1 else: if len(aval) != 0: preferred, ind = Q[p2][1], Q[p2][2] i = aval.bisect(preferred) cands = [] if i > 0: cands.append(aval[i1]) if i < len(aval): cands.append(aval[i]) ans[ind] = min(cands, key = lambda x: abs(x  preferred)) p2 += 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 }