Closest Room LeetCode solution in Python

1
# Runtime: 1741 ms (Top 100.0%) | Memory: 67.86 MB (Top 93.7%)
2

3

4
class Solution:
5
    def closestRoom(
6
        self, rooms: List[List[int]], queries: List[List[int]]
7
    ) -> List[int]:
8
        ans = [0] * len(queries)
9

10
        # sort queries to handle largest size queries first
11
        q = deque(
12
            sorted(
13
                [(size, room, i) for i, (room, size) in enumerate(queries)],
14
                key=lambda a: (-a[0], a[1], a[2]),
15
            )
16
        )
17

18
        # sort rooms by descending size
19
        rooms = deque(sorted(rooms, key=lambda x: -x[1]))
20

21
        # current available room ids
22
        cands = []
23

24
        while q:
25
            size, room, i = q.popleft()
26
            # add room ids to candidates as long as top of room size meet the requirements
27
            while rooms and rooms[0][1] >= size:
28
                bisect.insort(cands, rooms.popleft()[0])
29

30
            # if no room size available, return -1
31
            if not cands:
32
                ans[i] = -1
33

34
            # else use bisect to find optimal room ids
35
            else:
36
                loc = bisect.bisect_left(cands, room)
37
                if loc == 0:
38
                    ans[i] = cands[loc]
39
                elif loc == len(cands):
40
                    ans[i] = cands[-1]
41
                else:
42
                    ans[i] = (
43
                        cands[loc - 1]
44
                        if room - cands[loc - 1] <= cands[loc] - room
45
                        else cands[loc]
46
                    )
47

48
        return ans