Python - SortedList + BinarySearch Approach ✅
Why are we sorting the Queries based on the "MinSize" in Decreasing order? \n\nBecause if you think, if for the query with the biggest value of "minSize", we ca
Why are we sorting the Queries based on the "MinSize" in Decreasing order? \n\nBecause if you think, if for the query with the biggest value of "minSize", we can create a list of candidate rooms, then that list will be valid for every other query. We may add some more rooms in that for other queries, but the list for previous query will be valid for next one as well.\n\nAnd only from that list itself, we will get any valid roomId for any query. So, the main thing is to construct this list of candidate rooms from which we have to find the one we are looking for.\n\nLet\'s understand it with an example. \n\n\t\trooms = [[1,4],[2,3],[3,5],[4,1],[5,2]]\n\t\tqueries = [[2,3],[2,4],[2,5]]\n\t\t\n\t\tWe will sort "queries" in decreasing order based on "minSize"\n\t\tAnd since the final output list is constructed based on the queries, we also keep the original indices\n\t\t\n\t\tSo, we convert each query to a tuple (minSize, preferred, index)\n\t\t\n\t\tAnd then we sort in decreasing order. So now, queries become - \n\t\t\n\t\tqueries = [(5,2,2), (4,2,1), (3,2,0)]\n\t\t\n\t\tNow, we can create a candidate list where we keep all those rooms that may be the solutions for this query.\n\t\t\n\t\tSuppose, we have the first query (5,2,2)\n\t\t\n\t\tThen here, we have minSize = 5, preferred = 2 and index = 2\n\t\t\n\t\tSo, all those rooms for which size >= 5 are all valid solutions for this query.\n\t\t\n\t\tAnd we only have one room that satisfies this condition -> [[3,5]]\n\t\t\n\t\tNow, to quickly create candidate list, we can sort the rooms in decreasing order based on size as well.\n\t\t\n\t\tSo that as soon as we get to a room that is not valid, we know all rooms after it are not valid as well so we stop.\n\t\t\n\t\tAnd once we have the candidates, all we are looking for is the room with the roomId that is closest to "preferred"\n\t\t\n\t\t\nBecause, abs(id - preferred) will be minimized if "id" is closest to "preferred" value. And that means, we need to Binary search for the "floor" and "ceil" value of "preferred" in candidates list. Because either floor or ceil or both are closest to "preferred". In case of a tie, we can choose the "floor" value.\n\n\n```\nfrom sortedcontainers import SortedList \nclass Solution:\n    def closestRoom(self, rooms: List[List[int]], queries: List[List[int]]) -> List[int]:\n        \n        k = len(queries)\n\n        answer = [-1] * k\n        \n        # Sort the rooms based on their size in Decreasing order\n        rooms.sort(key = lambda x: x[1], reverse=True)\n        \n        # Sort the Queries by the minSize but in decreasing order\n        # Because if for the query with biggest minSize value, we can create a Sortedlist of valid rooms\n        # That list can then be used for every query that has a smaller of equal minSize\n        \n        # Also, since the "answer" has elements in same order as queries originally\n        # WE do not want to lose track of original indices\n        queries = [(query[1], query[0], i) for i,query in enumerate(queries)]\n        \n        # Now sort based on the MinSize in Decreasing order\n        queries.sort(reverse=True)\n        \n        # List of valid rooms that can be the candidates\n        candidates = SortedList()\n        \n        j = 0\n        \n        # For each query\n        for minSize, preferred, i in queries:\n            # Create the candidate list\n            while j < len(rooms) and rooms[j][1] >= minSize:\n                candidates.add(rooms[j][0])\n                j += 1\n                \n            # Now, among these candidate rooms, we will search for the id that is closest to "preferred"\n            # The id closest to "preferred" will be either floor or ceil of "preferred" in the candidates list\n            # for that, we will use binary search\n            \n            # First, let\'s find the floor\n            # That is, the biggest id that is <= "preferred"\n            start = 0\n            end = len(candidates) - 1\n            floorIdx = -1\n            \n            while start <= end:\n                mid = start + (end - start) // 2\n            \n                if candidates[mid] <= preferred:\n                    floorIdx = mid\n                    start = mid + 1\n                else: end = mid - 1\n                    \n            # Next, let\'s find the ceil\n            # That is, the smallest id that is >= "preferred"\n            start = 0\n            end = len(candidates) - 1\n            ceilIdx = -1\n            \n            while start <= end:\n                mid = start + (end - start) // 2\n            \n                if candidates[mid] >= preferred:\n                    ceilIdx = mid\n                    end = mid - 1\n                else: start = mid + 1\n            \n            # If both are -1, then there is no valid room available\n            if floorIdx == -1 and ceilIdx == -1: answer[i] = -1\n            else: \n                diff1 = abs(candidates[floorIdx] - preferred)\n                diff2 = abs(candidates[ceilIdx] - preferred)\n                \n                answer[i] = candidates[floorIdx] if diff1 <= diff2 else candidates[ceilIdx]     \n        \n        return answer\n```
['Binary Search', 'Binary Tree', 'Python']