Skip to content

1847. Closest Room

Difficulty Topics

Description

There is a hotel with n rooms. The rooms are represented by a 2D integer array rooms where rooms[i] = [roomIdi, sizei] denotes that there is a room with room number roomIdi and size equal to sizei. Each roomIdi is guaranteed to be unique.

You are also given k queries in a 2D array queries where queries[j] = [preferredj, minSizej]. The answer to the jth query is the room number id of a room such that:

  • The room has a size of at least minSizej, and
  • abs(id - preferredj) is minimized, where abs(x) is the absolute value of x.

If there is a tie in the absolute difference, then use the room with the smallest such id. If there is no such room, the answer is -1.

Return an array answer of length k where answer[j] contains the answer to the jth query.

 

Example 1:

Input: rooms = [[2,2],[1,2],[3,2]], queries = [[3,1],[3,3],[5,2]]
Output: [3,-1,3]
Explanation: The answers to the queries are as follows:
Query = [3,1]: Room number 3 is the closest as abs(3 - 3) = 0, and its size of 2 is at least 1. The answer is 3.
Query = [3,3]: There are no rooms with a size of at least 3, so the answer is -1.
Query = [5,2]: Room number 3 is the closest as abs(3 - 5) = 2, and its size of 2 is at least 2. The answer is 3.

Example 2:

Input: rooms = [[1,4],[2,3],[3,5],[4,1],[5,2]], queries = [[2,3],[2,4],[2,5]]
Output: [2,1,3]
Explanation: The answers to the queries are as follows:
Query = [2,3]: Room number 2 is the closest as abs(2 - 2) = 0, and its size of 3 is at least 3. The answer is 2.
Query = [2,4]: Room numbers 1 and 3 both have sizes of at least 4. The answer is 1 since it is smaller.
Query = [2,5]: Room number 3 is the only room with a size of at least 5. The answer is 3.

 

Constraints:

  • n == rooms.length
  • 1 <= n <= 105
  • k == queries.length
  • 1 <= k <= 104
  • 1 <= roomIdi, preferredj <= 107
  • 1 <= sizei, minSizej <= 107

Solution

closest-room.py
from sortedcontainers import SortedList

class Solution:
    def closestRoom(self, rooms, queries):
        Q = sorted([(y, x, i) for i, (x,y) in enumerate(queries)])[::-1]
        R = sorted((y, x) for x, y in rooms)[::-1]
        n, q = len(R), len(Q)
        p1, p2, aval, ans = 0, 0, SortedList(), [-1]*q

        while p1 <= n and p2 < q:
            if p1 < n and R[p1][0] >= Q[p2][0]:
                aval.add(R[p1][1])
                p1 += 1
            else:
                if len(aval) != 0:
                    preferred, ind = Q[p2][1], Q[p2][2]
                    i = aval.bisect(preferred)

                    cands = []
                    if i > 0: cands.append(aval[i-1])
                    if i < len(aval): cands.append(aval[i])
                    ans[ind] = min(cands, key = lambda x: abs(x - preferred))

                p2 += 1

        return ans