1847. Closest Room


Problem Description

This problem involves a hotel with n unique rooms, each room represented by its room number and size. Given a list of k queries, each including a preferred room number and a minimum room size, the task is to find the room that best matches the queries' criteria: the room size must be at least the minimum size given in the query, and the room number must be as close as possible to the preferred room number specified in the query. If two rooms are equally close to the preferred number, the room with the smaller number should be chosen. If no suitable room exists, the answer for that query is -1. The goal is to return an array of answers for each of the k queries based on these conditions.

Intuition

To approach this solution, sorting and binary search are key techniques. The fundamental idea is to first sort the rooms by size, which allows us to efficiently eliminate rooms that are too small for a given query. After filtering out the too-small rooms, we need a way to find the closest room number to the preferred one quickly. A binary search can help with this, and a data structure like a sorted list will allow us to use binary search effectively.

Here's the process we'll follow:

  1. Sort the rooms by size in non-decreasing order. This will help us later when we need to filter out rooms that are too small for a query and is the reason why rooms are processed starting with the largest size first.
  2. Create a sorted list of just the room numbers. This list will be dynamically updated as we iterate through the queries and remove rooms that don't meet the size requirement.
  3. Sort the queries by their minimum size in non-decreasing order and keep track of their original indices. Sorting the queries ensures we only have to remove rooms that are too small once for the smallest minSize rather than redoing it for each individual query.
  4. Iterate through the sorted queries and perform the following steps:
    • For a given query, remove rooms that are too small from the sorted list we created earlier. Once a room is removed for one query, there's no need to consider it for the later queries since we sorted the queries by minimum size already.
    • Use binary search to find the room number closest to the preferred one. If it's a tie (equal distance to two room numbers), the binary search helps find the smaller room number.
    • Store the result in the appropriate spot in the answer array by using the original index of the query.

This way, we are leveraging efficient sorting and searching algorithms to minimize both the time we spend on each query and the number of rooms we have to consider.

Solution Approach

In the provided solution, the implementation leverages Python's sorting capabilities, as well as the SortedList data structure from the sortedcontainers package, which maintains the elements in sorted order and supports efficient insertion and removal operations.

Here are the steps detailing the implementation:

  1. Sorting the Rooms: The first step is to sort the list of rooms by their size. This is done with the help of a lambda function that serves as a key for the sorting algorithm. The rooms are sorted in ascending order based on size (x[1] being the size of the room).

    1rooms.sort(key=lambda x: x[1])
  2. Preparing for Queries: In preparation for processing the queries, the solution sorts the indices of the queries array based on the minimum size required for each query. This is so that we process queries with the smallest required sizes first.

    1idx = sorted(range(k), key=lambda i: queries[i][1])
  3. Creating a Sorted List of Room Numbers: A SortedList is created consisting of all the room numbers from the sorted rooms array. As the elements in SortedList are kept in sorted order, it allows us to use efficient operations like bisect_left, which is essentially a binary search to find the appropriate insertion point (or the closest element) for a given value.

    1sl = SortedList(x[0] for x in rooms)
  4. Processing the Queries: The for loop iterates over the queries sorted by size, for each query doing the following:

    • Increasing Room Size Cut-off: Any rooms that are too small (rooms[i][1] < minSize) for the current query are removed from the sorted list. Increasing the index i as we go ensures that we never look back at the smaller rooms for future queries, as the queries themselves are sorted by size.

      1while i < n and rooms[i][1] < minSize:
      2    sl.remove(rooms[i][0])
      3    i += 1
    • Binary Search for Closest Room: Using sl.bisect_left(prefer), we find the position where the preferred room number would be inserted into the SortedList. We then use this position to find the closest room number that still meets the size requirements.

      1p = sl.bisect_left(prefer)
    • Finding the Best Match: There are now two possibilities: the room number at position p and the room number immediately before p (if p is not the first element). Between these two, we choose the one that is closest to the preferred number (and if the distances are the same, the smaller room number is chosen). If p is at the end of the sorted list, we only consider the room number before p.

      1if p < len(sl):
      2    ans[j] = sl[p]
      3if p and (ans[j] == -1 or ans[j] - prefer >= prefer - sl[p - 1]):
      4    ans[j] = sl[p - 1]
  5. Formatting the Result: Finally, the answer for each query is stored in the ans array, which is returned at the end of the function.

    1return ans

The use of a SortedList for room numbers, sorted queries based on room size requirements, and binary search to find the closest room number are key features of this approach that make it efficient for processing multiple queries against a potentially large list of rooms.

Example Walkthrough

Let's consider a small example to illustrate the solution approach:

Assume we have the following hotel rooms and queries:

  • Hotel rooms:

    • Room 101 with size 300
    • Room 102 with size 200
    • Room 103 with size 400
    • Room 104 with size 500
  • Queries:

    • Query 1: Prefer room 105, with minimum size 200
    • Query 2: Prefer room 102, with minimum size 300

According to the solution approach, here's how this plays out:

  1. Sorting the Rooms: The rooms are sorted by size:

    Before sorting: [101, 300], [102, 200], [103, 400], [104, 500]

    After sorting: [102, 200], [101, 300], [103, 400], [104, 500]

  2. Preparing for Queries: We sort the queries by their minimum size requirement:

    Before sorting: Query 1: [105, 200], Query 2: [102, 300]

    After sorting: Query 1: [105, 200], Query 2: [102, 300]

  3. Creating a Sorted List of Room Numbers: A SortedList is created with room numbers:

    SortedList: [102, 101, 103, 104]

  4. Processing the Queries:

    • For Query 1 (prefer 105, min size 200):

      • No rooms are too small, all room sizes are greater than 200.
      • Perform binary search for the closest room to 105:
        • p is assigned the position where 105 would be inserted, which is at the end of the list.
        • Since p equals the length of the list, we only consider the last room number before p, which is 104.
        • The best match for Query 1 is room 104.
    • Move to Query 2 (prefer 102, min size 300):

      • Room 102 is removed because its size is less than 300.
      • Updated SortedList: [101, 103, 104]
      • Perform binary search for the closest room to 102:
        • p is the position where 102 would be inserted, which is at the start.
        • At p, the room number is 101.
        • Since p is not at the end, we consider the next room number (103) and compare distances.
        • Room 101 is closer to 102 than room 103, so the best match for Query 2 is room 101.
  5. Formatting the Result:

    • The answers array for the queries in their original order is [104, 101].

The above step-by-step process demonstrates how the solution filters out unsuitable rooms and efficiently arrives at the closest room number that satisfies each query's conditions.

Python Solution

1from sortedcontainers import SortedList
2from typing import List
3
4class Solution:
5    def closestRoom(self, rooms: List[List[int]], queries: List[List[int]]) -> List[int]:
6        # Sort rooms by size in ascending order
7        rooms.sort(key=lambda room: room[1])
8
9        num_queries = len(queries)
10        # Sorting indices of the queries by the size in ascending order
11        sorted_query_indices = sorted(range(num_queries), key=lambda i: queries[i][1])
12
13        # Initialize answer list with -1, assuming no valid room is found for the queries
14        answers = [-1] * num_queries
15
16        current_room_index = 0
17        num_rooms = len(rooms)
18
19        # Initializing a SortedList object to keep track of room IDs in sorted order
20        sorted_room_ids = SortedList(room[0] for room in rooms)
21
22        # Process the queries in the order of their size requirements
23        for query_index in sorted_query_indices:
24            preferred_id, min_size = queries[query_index]
25
26            # Remove rooms that are smaller than the minimum size from the sorted list
27            while current_room_index < num_rooms and rooms[current_room_index][1] < min_size:
28                sorted_room_ids.remove(rooms[current_room_index][0])
29                current_room_index += 1
30
31            # If all rooms are smaller than the minimum size, break
32            if current_room_index == num_rooms:
33                break
34
35            # Find the closest room ID that is equal or larger than the preferred ID
36            pos = sorted_room_ids.bisect_left(preferred_id)
37            # If such a room exists, set it as the answer for the current query
38            if pos < len(sorted_room_ids):
39                answers[query_index] = sorted_room_ids[pos]
40
41            # Check if the room before is actually closer to the preferred ID
42            # Update the answer for the current query if it is closer
43            if pos > 0 and (answers[query_index] == -1 or
44                            answers[query_index] - preferred_id >= preferred_id - sorted_room_ids[pos - 1]):
45                answers[query_index] = sorted_room_ids[pos - 1]
46
47        # Return the list of closest room IDs for each query
48        return answers
49

Java Solution

1import java.util.Arrays;
2import java.util.TreeMap;
3
4class Solution {
5    public int[] closestRoom(int[][] rooms, int[][] queries) {
6        // Number of rooms
7        int numberOfRooms = rooms.length;
8        // Number of queries
9        int numberOfQueries = queries.length;
10
11        // Sort the rooms by size in ascending order
12        Arrays.sort(rooms, (a, b) -> a[1] - b[1]);
13
14        // Create an array of query indices
15        Integer[] queryIndices = new Integer[numberOfQueries];
16        for (int i = 0; i < numberOfQueries; i++) {
17            queryIndices[i] = i;
18        }
19
20        // Sort the query indices based on the room size preference from the queries in ascending order
21        Arrays.sort(queryIndices, (i, j) -> queries[i][1] - queries[j][1]);
22
23        // Room index for traversing the sorted rooms
24        int roomIndex = 0;
25        // TreeMap for keeping track of available rooms (key is room ID, value is a count which is not used here)
26        TreeMap<Integer, Integer> availableRooms = new TreeMap<>();
27        // Initialize the TreeMap with all rooms
28        for (int[] room : rooms) {
29            availableRooms.put(room[0], 1); // Since map value is not used, just set to 1
30        }
31
32        // Array for storing answers to the queries
33        int[] answers = new int[numberOfQueries];
34        // Initialize answers with -1 (which indicates no room found for the query)
35        Arrays.fill(answers, -1);
36
37        // Iterate through each query by sorted room size preference
38        for (int queryIndex : queryIndices) {
39            // Preferred room id and the minimum size required from the query
40            int preferredID = queries[queryIndex][0], minSize = queries[queryIndex][1];
41
42            // Remove rooms from the TreeMap that are smaller than the current query's minimum size requirement
43            while (roomIndex < numberOfRooms && rooms[roomIndex][1] < minSize) {
44                int roomId = rooms[roomIndex][0];
45                if (availableRooms.merge(roomId, -1, Integer::sum) == 0) {
46                    availableRooms.remove(roomId);
47                }
48                ++roomIndex;
49            }
50
51            // If no rooms are available that satisfy the size constraint, move on to the next query
52            if (roomIndex == numberOfRooms) {
53                break;
54            }
55
56            // Find the closest room with at least the preferred room ID
57            Integer ceilingKey = availableRooms.ceilingKey(preferredID);
58            if (ceilingKey != null) {
59                answers[queryIndex] = ceilingKey;
60            }
61
62            // Find the closest room with no more than the preferred room ID
63            Integer floorKey = availableRooms.floorKey(preferredID);
64            if (floorKey != null && (answers[queryIndex] == -1 || answers[queryIndex] - preferredID >= preferredID - floorKey)) {
65                // Update the answer if floorKey is closer or equally close to preferred ID compared to ceilingKey
66                answers[queryIndex] = floorKey;
67            }
68        }
69        return answers;
70    }
71}
72

C++ Solution

1#include <vector>
2#include <algorithm>
3#include <set>
4#include <numeric>
5
6using namespace std;
7
8class Solution {
9public:
10    vector<int> closestRoom(vector<vector<int>>& rooms, vector<vector<int>>& queries) {
11        // Sort room based on their size in ascending order
12        sort(rooms.begin(), rooms.end(), [](const vector<int>& a, const vector<int>& b) {
13            return a[1] < b[1];
14        });
15
16        // Store the size of 'rooms' and 'queries' arrays
17        int numRooms = rooms.size();
18        int numQueries = queries.size();
19
20        // Create an index array for queries and fill it with ascending integers starting at 0
21        vector<int> queryIndices(numQueries);
22        iota(queryIndices.begin(), queryIndices.end(), 0);
23
24        // Sort the indices of 'queries' based on the room size requirement
25        sort(queryIndices.begin(), queryIndices.end(), [&](int i, int j) {
26            return queries[i][1] < queries[j][1];
27        });
28
29        // Initialize the answer vector with -1 indicating no room found
30        vector<int> answers(numQueries, -1);
31
32        // Multiset to store the ids of available rooms
33        multiset<int> availableRoomIds;
34        for (const auto& room : rooms) {
35            availableRoomIds.insert(room[0]);
36        }
37
38        // Keep track of the current position in the sorted 'rooms' array
39        int currentRoomIndex = 0;
40
41        // Iterate through the sorted query indices
42        for (int queryIndex : queryIndices) {
43            // Fetch the preferred room id and the required size from 'queries'
44            int preferredRoomId = queries[queryIndex][0];
45            int minSizeReq = queries[queryIndex][1];
46
47            // Remove rooms that are too small from our availableRoomIds
48            while (currentRoomIndex < numRooms && rooms[currentRoomIndex][1] < minSizeReq) {
49                availableRoomIds.erase(availableRoomIds.find(rooms[currentRoomIndex][0]));
50                ++currentRoomIndex;
51            }
52
53            // If all rooms have been checked, exit the loop
54            if (currentRoomIndex == numRooms) {
55                break;
56            }
57
58            // Find the first room id in the set that is not less than the preferred id
59            auto closestRoomIt = availableRoomIds.lower_bound(preferredRoomId);
60
61            // Check if there is an available room id greater or equal to the preferred id
62            if (closestRoomIt != availableRoomIds.end()) {
63                answers[queryIndex] = *closestRoomIt;
64            }
65
66            // Check for a closer room id that is less than the preferred id
67            if (closestRoomIt != availableRoomIds.begin()) {
68                auto prevRoomIt = prev(closestRoomIt); // Get iterator to the previous element
69                if (answers[queryIndex] == -1 ||
70                    abs(*prevRoomIt - preferredRoomId) <= abs(answers[queryIndex] - preferredRoomId)) {
71                    answers[queryIndex] = *prevRoomIt;
72                }
73            }
74        }
75        // Return the answers vector containing the id of the closest room for each query
76        return answers;
77    }
78};
79

Typescript Solution

1function closestRoom(rooms: number[][], queries: number[][]): number[] {
2  // Sort rooms based on their size in ascending order
3  rooms.sort((a, b) => a[1] - b[1]);
4
5  // Store the number of rooms and queries
6  const numRooms = rooms.length;
7  const numQueries = queries.length;
8
9  // Create an index array for queries with indices from 0 to numQueries-1
10  const queryIndices: number[] = Array.from(Array(numQueries).keys());
11
12  // Sort the indices of queries based on the room size requirement
13  queryIndices.sort((i, j) => queries[i][1] - queries[j][1]);
14
15  // Initialize the answers array with -1, indicating no room found
16  const answers: number[] = new Array(numQueries).fill(-1);
17
18  // Set to store the IDs of available rooms
19  const availableRoomIds: Set<number> = new Set(rooms.map(room => room[0]));
20
21  // Keep track of the current position in the sorted rooms array
22  let currentRoomIndex = 0;
23
24  // Iterate through the sorted query indices
25  for (const queryIndex of queryIndices) {
26    // Fetch the preferred room ID and the minimum required size
27    const [preferredRoomId, minSizeReq] = queries[queryIndex];
28
29    // Remove ineligible rooms that are too small
30    while (currentRoomIndex < numRooms && rooms[currentRoomIndex][1] < minSizeReq) {
31      availableRoomIds.delete(rooms[currentRoomIndex][0]);
32      currentRoomIndex++;
33    }
34
35    // Break early if all rooms have been checked
36    if (currentRoomIndex === numRooms) {
37      break;
38    }
39
40    // Array conversion for two-pointer technique since Sets do not have random access
41    const availableRoomIdsArray = Array.from(availableRoomIds);
42
43    // Find the closest room ID that is not less than the preferred ID
44    const insertIndex = sortedIndex(availableRoomIdsArray, preferredRoomId);
45
46    // Check if there's an available room ID greater or equal to the preferred ID
47    if (insertIndex < availableRoomIds.size) {
48      answers[queryIndex] = availableRoomIdsArray[insertIndex];
49    }
50
51    // Check for a closer room ID that is less than the preferred ID
52    if (insertIndex > 0) {
53      const previousRoomId = availableRoomIdsArray[insertIndex - 1];
54      if (
55        answers[queryIndex] === -1 ||
56        Math.abs(previousRoomId - preferredRoomId) <= Math.abs(answers[queryIndex] - preferredRoomId)
57      ) {
58        answers[queryIndex] = previousRoomId;
59      }
60    }
61  }
62
63  // Return the answers array containing the IDs of the closest room for each query
64  return answers;
65}
66
67// Helper function to return the index at which the `value` would be inserted into the `array`
68// ensuring ascending order. It uses binary search for efficiency.
69function sortedIndex(array: number[], value: number): number {
70  let low = 0,
71    high = array.length;
72
73  while (low < high) {
74    const mid = (low + high) >>> 1;
75    if (array[mid] < value) {
76      low = mid + 1;
77    } else {
78      high = mid;
79    }
80  }
81  return low;
82}
83

Time and Space Complexity

The code snippet above defines a class Solution that contains a method closestRoom used to find the closest room to the preferred room that also meets the minimum size requirement.

Time Complexity:

Let m be the length of the rooms list and n be the length of the queries list.

  1. Sorting the rooms list by size takes O(m log m).
  2. Sorting the indices of the queries by the room size requirement takes O(n log n).
  3. The SortedList construction from all rooms involves adding each room once, which takes O(m log m).
  4. Iterating through queries indices (after sorting by size):
    • The while loop can, in the worst case, remove each room once (thus, it runs a total of m times over all iterations). Removal in a SortedList is O(log m), so the total cost of removals is O(m log m).
    • For each query, the bisect_left operation in the SortedList is O(log m), which is done at most once per query.
    • Accessing len(sl) is O(1).
    • The conditionals and value assignments are O(1).

Combining these parts, we can estimate the overall worst-case time complexity as:

1O(m log m) + O(n log n) + O(m log m) + n * O(log m)
2= O(m log m) + O(n log n) + O(n log m)
3= O((m + n) log m) + O(n log n)

Since m log m can be larger than n log n or vice versa depending on the input, we take the highest term:

1= O(max(m, n) log m)

Note that when m is much larger than n, m log m becomes the dominant term, and when n is much larger, the two terms contribute significantly and the overall complexity could be approximated by adding both terms.

Space Complexity:

  1. We use additional memory for the sorted rooms, which is O(m) space.
  2. The SortedList, which initially contains m ids, also uses O(m) space.
  3. The ans array is of size n, which uses O(n) space.

Thus the total space complexity is:

1O(m) + O(m) + O(n) = O(m + n)

This is because m and n are independent and could vary significantly.


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫