LeetCode Solutions Blog

Closest Room

Number: 1957

Difficulty: Hard

Paid? No

Companies: Amazon

Problem Description

We are given a list of hotel rooms where each room is represented by an id and a size. For each query consisting of a preferred id and a minimum room size requirement, we must pick the room with size at least the minimum such that the absolute difference between its id and the preferred id is minimized. In the event of a tie, the room with the smaller id is chosen. If no room meets the minimum size requirement, return -1.

Key Insights

Sort the rooms based on their sizes in descending order.
Sort the queries in descending order by the required minSize so that we progressively add qualified rooms.
Use an ordered (balanced) set keyed by room id (or a sorted array with binary search) to quickly find the room id closest to the preferred value.
For each query, binary search in the ordered set for the closest candidate on both sides (predecessor and successor) and then pick the one with the smallest absolute difference.

Space and Time Complexity

Time Complexity: O((n + k) log n) where n is the number of rooms and k is the number of queries
Space Complexity: O(n + k) for storing the rooms, queries, and the ordered data structure.

Solution

We can solve the problem offline by processing queries in decreasing order of minSize and simultaneously adding all the rooms that satisfy the size requirement into an ordered set (or sorted list). For each query, after inserting all eligible rooms, we use binary search on the ordered set to locate the closest room id to the preferred id. We then check the neighbor keys (if available) to determine which room yields the smallest absolute difference to the preferred id, ensuring that ties are resolved by the smaller room id.

Code Solutions

import bisect

def closestRoom(rooms, queries):
    n = len(rooms)
    k = len(queries)
    # Pair each query with its original index so that we can restore the order later.
    indexed_queries = [(minSize, preferred, idx) for idx, (preferred, minSize) in enumerate(queries)]
    # Sort queries in descending order by minSize.
    indexed_queries.sort(key=lambda x: -x[0])
    # Sort rooms in descending order by size.
    rooms.sort(key=lambda x: -x[1])
    
    result = [-1] * k
    available_room_ids = []  # will maintain sorted list of room ids
    j = 0  # pointer for rooms list
    
    # Process each query (minSize, preferred, idx)
    for minSize, preferred, idx in indexed_queries:
        # Add all rooms that satisfy the current query's size requirement.
        while j < n and rooms[j][1] >= minSize:
            roomId = rooms[j][0]
            bisect.insort(available_room_ids, roomId)
            j += 1
        if not available_room_ids:
            result[idx] = -1
        else:
            # binary search to find the insertion point
            pos = bisect.bisect_left(available_room_ids, preferred)
            candidate = None
            # check candidate on right side if exists
            if pos < len(available_room_ids):
                candidate = available_room_ids[pos]
            # check candidate on left side and decide which is closer
            if pos > 0:
                left_candidate = available_room_ids[pos - 1]
                if candidate is None or abs(left_candidate - preferred) <= abs(candidate - preferred):
                    candidate = left_candidate
            result[idx] = candidate
    return result

# Example usage:
rooms = [[2,2],[1,2],[3,2]]
queries = [[3,1],[3,3],[5,2]]
print(closestRoom(rooms, queries))  # Output: [3,-1,3]