What is the best approach pattern for Closest Room?

Binary search over the valid answer space combined with sorting rooms and queries ensures fast nearest room lookup.

How do I handle multiple rooms equally close to the preferred room?

Always return the room with the smallest room number when absolute differences tie.

Can this approach handle large inputs efficiently?

Yes, sorting and maintaining an ordered set allow O((n + k) log n) performance suitable for n up to 10^5.

Why sort queries in descending minSize order?

Sorting allows incremental insertion of eligible rooms, ensuring only rooms meeting the current query's size are considered.

What data structure is ideal for finding the closest room quickly?

An ordered set or balanced BST enables efficient insertions and binary searches to find the closest room.

#1847

Hard

auto_awesome二分·搜索·答案·空间

LeetCode 题解工作台

最近的房间

一个酒店里有 n 个房间，这些房间用二维整数数组 rooms 表示，其中 rooms[i] = [roomId i , size i ] 表示有一个房间号为 roomId i 的房间且它的面积为 size i 。每一个房间号 roomId i 保证是独一无二的。同时给你 k 个查询，用二维数组…

数组二分查找排序有序集合

题目描述

一个酒店里有 n 个房间，这些房间用二维整数数组 rooms 表示，其中 rooms[i] = [roomId_i, size_i] 表示有一个房间号为 roomId_i 的房间且它的面积为 size_i 。每一个房间号 roomId_i 保证是 独一无二 的。

同时给你 k 个查询，用二维数组 queries 表示，其中 queries[j] = [preferred_j, minSize_j] 。第 j 个查询的答案是满足如下条件的房间 id ：

房间的面积至少为 minSize_j ，且
abs(id - preferred_j) 的值最小，其中 abs(x) 是 x 的绝对值。

如果差的绝对值有相等的，选择最小的 id 。如果 没有满足条件的房间 ，答案为 -1 。

请你返回长度为 k 的数组 answer ，其中 answer[j] 为第 j 个查询的结果。

示例 1：

输入：rooms = [[2,2],[1,2],[3,2]], queries = [[3,1],[3,3],[5,2]]
输出：[3,-1,3]
解释：查询的答案如下：
查询 [3,1] ：房间 3 的面积为 2 ，大于等于 1 ，且号码是最接近 3 的，为 abs(3 - 3) = 0 ，所以答案为 3 。
查询 [3,3] ：没有房间的面积至少为 3 ，所以答案为 -1 。
查询 [5,2] ：房间 3 的面积为 2 ，大于等于 2 ，且号码是最接近 5 的，为 abs(3 - 5) = 2 ，所以答案为 3 。

示例 2：

输入：rooms = [[1,4],[2,3],[3,5],[4,1],[5,2]], queries = [[2,3],[2,4],[2,5]]
输出：[2,1,3]
解释：查询的答案如下：
查询 [2,3] ：房间 2 的面积为 3 ，大于等于 3 ，且号码是最接近的，为 abs(2 - 2) = 0 ，所以答案为 2 。
查询 [2,4] ：房间 1 和 3 的面积都至少为 4 ，答案为 1 因为它房间编号更小。
查询 [2,5] ：房间 3 是唯一面积大于等于 5 的，所以答案为 3 。

提示：

n == rooms.length
1 <= n <= 10⁵
k == queries.length
1 <= k <= 10⁴
1 <= roomId_i, preferred_j <= 10⁷
1 <= size_i, minSize_j <= 10⁷

lightbulb

解题思路

方法一：离线查询 + 有序集合 + 二分查找

我们注意到，查询的顺序并不影响答案，而且题目中涉及到房间面积的大小关系，因此，我们可以将查询按照最小面积从小到大排序，这样我们就可以从小到大依次处理每个查询。另外，我们也将房间按照面积从小到大排序。

接下来，我们创建一个有序列表，将所有房间的编号加入有序列表中。

然后，我们从小到大依次处理每个查询。对于每个查询，我们首先将所有面积小于等于当前查询的最小面积的房间从有序列表中移除。然后，我们在剩余的房间中，使用二分查找找到最接近当前查询的房间编号。如果不存在这样的房间，那么我们就返回 $-1$ 。

时间复杂度 $O(n \times \log n + k \times \log k)$ ，空间复杂度 $O(n + k)$ 。其中 $n$ 和 $k$ 分别是房间数和查询数。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

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

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Consider sorting queries to optimize the closest room search for larger sizes.
question_mark
Think about using a data structure supporting fast nearest neighbor queries.
question_mark
Check tie-breaking rules carefully; returning the smallest room ID is required.

warning

常见陷阱

外企场景

error
Ignoring tie-breaking by smallest room number leads to wrong answers.
error
Processing queries without sorting can cause inefficient searches or incorrect eligibility.
error
Not maintaining a dynamic set of valid rooms causes missed or incorrect matches.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Find closest room but maximize room size instead of minimizing absolute difference.
arrow_right_alt
Queries include a range of preferred rooms instead of a single preferred number.
arrow_right_alt
Return multiple closest rooms when more than one satisfies the distance and size constraints.

help

常见问题

外企场景

继续练习

#1818 绝对差值和 #2251 花期内花的数目 #2659 将数组清空