Leetcode1847：最近的房间

题目描述： 

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

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

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

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

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

代码思路：

 代码实现：

from sortedcontainers import SortedSet
class Solution:
    def closestRoom(self, rooms: List[List[int]], queries: List[List[int]]) -> List[int]:
        rooms.sort(key = lambda r: -r[1])   #按照size从大到小排序
        rn = len(rooms)
    
        qn = len(queries)
        for i in range(qn):
            queries[i].append(i)        #加上index。在进res时按照index放置
        queries.sort(key = lambda q: -q[1]) #按照minSize从大到小排列
        
        res = [0 for _ in range(qn)]
        INF = 10 ** 9   #哨兵
        window = SortedSet()
        window.add(-INF)
        window.add(INF)
        ri = 0
        for preferID, minSize, qID in queries:
            while ri < rn and rooms[ri][1] >= minSize:  #房间的size比minSize大
                window.add(rooms[ri][0])     #房间号入window 
                ri += 1
            idxR = window.bisect_left(preferID)
            idxL = idxR - 1
            L, R = window[idxL] , window[idxR]
            res[qID] = L if (preferID - L) <= (R - preferID) else R
            if res[qID] in (-INF, INF):
                res[qID] = -1
        return res