[Python] O(n log n): Sort the rooms and queries first, commented
Explanation:\nThe question requires making two crucial observations. A naive approach would sort the rooms by id first, and binary search each query\'s preferre
**Explanation:**\nThe question requires making two crucial observations. A naive approach would sort the rooms by id first, and binary search each query\'s preferred id in the rooms, then iterate over rooms until we found one of the right size. \n\nUnfortunately, this leads to an O(n^2) algorithm if we have to walk the entire list. Let\'s make some observations and do better. Here are the most important steps.\n\n1. (**CRUCIAL**) If we sort both the rooms and queries by their size, we can **limit our query searches to only rooms of the right size**. If the filtered rooms are maintained in sorted order of ID, we can use an O(log n) binary search to find the closest or 2 closest rooms to our preferred ID.\n\n2. We need to add rooms of varying ID\'s to our list dynamically, maintaining sorted order. Using bisect.insort can cause up to O(n) insert time to the middle of our list. We need a data structure like a **balanced BST** or order statistic tree. While Python doesn\'t have this built-in, I\'m using the leetcode approved sortedcontainers library for an order statistic tree with O(log n) lookups and inserts. \n\n\nThat was the hard part. Now, we just need to track the original query ID\'s for our answers, as well as deal with the edge cases of whether to use the lower or higher ID, closest to the preferred value.\n\n\n**Python Code:**\n```python\nimport sortedcontainers\nclass Solution:\n    def closestRoom(self, rooms: List[List[int]], queries: List[List[int]]) -> List[int]:\n\n        # Sort rooms and queries in decreasing order of size\n        rooms.sort(key=lambda x: x[1], reverse=True)\n        sorted_queries = sorted(((i, pref, min_size) for i, (pref, min_size) in enumerate(queries)),\n                                key=lambda x: x[2], reverse=True)\n\n        ans = [-1] * len(queries)\n        id_list = sortedcontainers.SortedList()\n        room_index = 0\n\n        # Iterate over queries in decreasing order of size\n        for orig_query_ind, preferred, min_size in sorted_queries:\n\n            # Update our room id list, adding all rooms with size >= min_size\n            while room_index < len(rooms) and rooms[room_index][1] >= min_size:\n                my_id = rooms[room_index][0]\n                room_index += 1\n                id_list.add(my_id)\n\n            # Keep -1 as answer if (min_size is above all actual room sizes) i.e. id_list is empty\n            if not id_list:\n                continue\n\n            # Find index of the largest id <= preferred\n            rightmost_ind_less_or_equal = id_list.bisect_right(preferred) - 1\n\n            # If preferred id is smaller than the smallest existing id\n            if rightmost_ind_less_or_equal < 0:\n                ans[orig_query_ind] = id_list[0]\n                continue\n\n            # If preferred id is >= largest existing id\n            if rightmost_ind_less_or_equal == len(id_list) - 1:\n                ans[orig_query_ind] = id_list[rightmost_ind_less_or_equal]\n                continue\n\n            # Get value of left and right candidate ids\n            smaller_id_choice, larger_id_choice = id_list[rightmost_ind_less_or_equal:rightmost_ind_less_or_equal+2]\n\n            # Take larger id only if closer to preferred id\n            if abs(larger_id_choice - preferred) < abs(smaller_id_choice - preferred):\n                ans[orig_query_ind] = larger_id_choice\n            else:\n                ans[orig_query_ind] = smaller_id_choice\n\n        return ans\n```\n\n**Complexity Analysis:**\nTime complexity: **O(n log n)** for sorting, and the n inserts and lookups in our BST each cost log n.\nSpace complexity: O(n)\n\nFeel free to ask any questions. If you found this explanation helpful, upvotes are always appreciated :)
[]