1847.最近的房间

链接：1847.最近的房间
难度：Hard
标签：数组、二分查找、有序集合、排序
简介：请你返回长度为 k 的数组 answer ，其中 answer[j] 为第 j 个查询的结果。

题解 1 - python

• 编辑时间：2024-12-16
• 执行用时：233ms
• 内存消耗：58.32MB
• 编程语言：python
• 解法介绍：有序数组

from sortedcontainers import SortedList
class Solution:
    def closestRoom(self, rooms: List[List[int]], queries: List[List[int]]) -> List[int]:
        qn = len(queries)
        res = [inf] * qn
        sl = SortedList()
        rooms.sort(key = lambda v: v[1])
        for size, idx in sorted([(queries[i][1], i) for i in range(qn)], reverse = True):
            qidx = queries[idx][0]
            while rooms and rooms[-1][1] >= size:
                room = rooms.pop()
                sl.add(room[0])
            if len(sl):
                bidx = sl.bisect_left(qidx)
                if bidx != len(sl) and abs(sl[bidx] - qidx) < abs(qidx - res[idx]):
                    res[idx] = sl[bidx]
                if bidx != 0 and abs(sl[bidx - 1] - qidx) <= abs(qidx - res[idx]):
                    res[idx] = sl[bidx - 1]
        return [v if v != inf else -1 for v in res]