[Python] Sort the queries and the rooms by size in decreasing order. 2000ms
Sort the queries and the rooms by size from the largest to the smallest size, then initialize an empty array that will keep the rooms big enough for the current
Sort the queries and the rooms by size from the largest to the smallest size, then initialize an empty array that will keep the rooms big enough for the current querie, and is sorted by index ("rms" in my code).\nTo answer to the i-th querie update the array "rms" keeping it in order, then binary search for the preferred room and choose between the room found by the binary search and the one before.\n```\nclass Solution:\n    def closestRoom(self, rooms: List[List[int]], queries: List[List[int]]) -> List[int]:\n        ans = [None] * len(queries)\n        queries = sorted([(s, p, i) for i, (p, s) in enumerate(queries)], reverse = True)\n        rooms.sort(reverse = True, key = itemgetter(1, 0))\n        rms = [-1]    #the -1 helps handle the case when there are no rooms with the right size\n        j = 0\n        for s, p, i in queries:\n            while j < len(rooms) and rooms[j][1] >= s:\n                insort(rms, rooms[j][0])\n                j += 1\n            x = bisect_left(rms,p)\n            ans[i] = rms[x - 1] if (x == len(rms) or x != 1 and abs( rms[x - 1] - p) <= abs(rms[x] - p)) else rms[x]\n        return ans\n```\nRuntime: 2000 ms\nMemory Usage: 49.3 MB\nThis solution is based on the one by DBabichev. Check out his post too for further explaination.
['Array', 'Sorting', 'Binary Tree', 'Python']