1847. Closest Room

Обновлено: 2024-03-12
1 мин
[]

Содержание

LeetCode problem 1847

from sortedcontainers import SortedList


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])
        res = [-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):
                res[j] = sl[p]
            if p and (res[j] == -1 or res[j] - prefer >= prefer - sl[p - 1]):
                res[j] = sl[p - 1]
        return res