LC 1847. 最近的房间

https://leetcode-cn.com/problems/closest-room/

这题我写了两个版本。一个是区间树，一个是题解中的解法。

区间树的代码是在是没有办法看，但是思路很简单

构建 room id 区间树，树值是 max size.
不断去测试左边和右边的边界点，在这个边界范围内，size >= max size的

这个时间复杂度是 O(lgn * lgn * Q). 也好，权当做编程练习了。

再次证明，凡是这种区间树的，都可以变为处理事件的方式。这种处理事件的方式很类似 Marzullo算法，但是需要针对具体问题做变形。

把query也作为event嵌入其中
按照 size 逆序排列，这样可以维护可选 room_id 的集合
python3在leetcode平台上可以使用 `sortedcontainers` 这个库，里面的 `SortedList` 数据结构其实类似C++中的 std::set

class Solution:
    def closestRoom(self, rooms: List[List[int]], queries: List[List[int]]) -> List[int]:
        events = []

        for i in range(len(rooms)):
            rid, size = rooms[i]
            events.append((size, 0, rid, i))
        for i in range(len(queries)):
            rid, size = queries[i]
            events.append((size, 1, rid, i))

        events.sort(key=lambda x: (-x[0], x[1], x[2], x[3]))
        print(events)

        ans = [-1] * len(queries)

        from sortedcontainers import SortedList
        sl = SortedList()

        for ev in events:
            (size, type, rid, idx) = ev
            if type == 0:
                sl.add(rid)
            else:
                i = sl.bisect_left(rid)
                dist = 1 << 30
                res = -1
                for j in (i - 1, i, i + 1):
                    if 0 <= j < len(sl):
                        d = abs(sl[j] - rid)
                        if d < dist:
                            res = sl[j]
                            dist = d
                ans[idx] = res
        return ans