Python 3: FT 90%, TC O(Q log(Q) + (N+Q) log(N)), SC O(N + Q): SortedList/SortedSet
Intuition\n\nThis problem seems to basically require ordered collections.\n\n## The Pattern\n\nFor each query: among rooms with size >= minsize, we want the clo
# Intuition\n\nThis problem seems to basically require ordered collections.\n\n## The Pattern\n\nFor each query: among rooms with size `>= minsize`, we want the closest `id`.\n\nClosest `id` pretty much screams "binary search" because we need to support arbitrary `id` queries.\n\nThis is a kind of "closest item meeting a criterion" problem.\n\nThe pattern for these problems is\n* **sort by the value involving the criterion**\n* **sort queries by the criterion**\n* **as the criterion gets less strict, add elements to a sorted collection**\n* **answer each query by bisecting the sorted collection**\n\nUse this pattern when the criterion is "monotonic," such that once we start answering queries that are less strict, each option remains valid for all future queries.\n\nIn this case the criterion is size. By processing queries in order of `minsize` descending, once a room is at least as big as the current minsize, it remains at least as large for the rest of the problem. This way we never need to remove elements from the sorted collection. Otherwise it\'s a nightmare (and bad asymtptotic complexity) review all items in the collection and evaluate whether they still belong or not after each query.\n\n## Sorted Collections in Python\n\nYour only options, thanks to the de facto dictator of Python Guido van Rossum\'s insistence that Python have absolutely no sorted collections, are\n* the heapq module, not suitable here\n* the `sortedcontainers` 3rd party library: `SortedList` or `SortedSet` are excellent choices\n* some other third-party library\n* some nasty wrangling with segment trees\n  * map all the room ids to contiguous integers 1..n that are monotonic with those room ids\n  * then make min and max segment trees on these indices, the initial value is -1 meaning "room not seen yet"\n  * when rooms are available, map the room id to its index, and set its value in the tree to the room id\n  * now you can answer in `log(len(rooms))` time what the max id less than the preferred room is and min id at least the preferred room is\n\nEnjoy!\n\n# Complexity\n\nLet `N` be the number of rooms and `Q` be the number of queries.\n\n- Time complexity: `O(N log(N)) + Q log(Q) + Q*log(N))`\n  - `N log(N)` and `Q log(Q)`: sorting rooms by size, queries by `minsize`\n  - `Q log(N)`: for each query we bisect the `SortedList` to find the nearest room ids above and below, a `log(N)` operation\n\n- Space complexity: `O(N + Q)`\n  - sorting takes `O(N)` for sorting rooms and `O(Q)` for the query indices and sorting them; Python\'s sort is based on mergesort\n  - the ordered collection of rooms takes `O(N)` memory\n  - so no matter what sorting algo we pick we have `O(N+Q)` anyway\n\n\n# Code\n```\nfrom sortedcontainers import SortedList\n\nclass Solution:\n    def closestRoom(self, rooms: List[List[int]], queries: List[List[int]]) -> List[int]:\n        # rooms is [id, size] pairs\n        # queries are [preferred, min] pairs\n\n        # so we want the closest room size to preferred among those with size >= min\n        # binary search!\n\n        # AHHHH DIDN\'T READ THE PROBLEM CAREFULLY.\n\n        # among rooms with size >= minsize we want the one with the closest ID NUMBER, not the closest size\n\n        # as queries ask for higher sizes, we have more options for room ids\n        \n        # we want the max id among rooms with lower IDs and min id among rooms with >= id that are valid\n\n        # so maybe we process queries in order by minsize\n        # as minsize increases we gain more room options: add to a sorted collection of ids\n        # then we can bisect the sorted collection\n\n        # in stock Python we\'re extremely limited here, best we can do in iview time is conditional maxes with\n        # range trees, ugh\n\n        # with sortedcontainers we can have a SortedList for this\n\n        rooms.sort(key=lambda room: room[1], reverse=True) # by size desc\n        r = 0 # next room not yet added to the SortedList of ids\n\n        avail = SortedList() # list of ids\n        ans = [-1]*len(queries)\n        qidxs = list(range(len(queries)))\n        qidxs.sort(key=lambda i: queries[i][1], reverse=True) # proc in order of min size desc\n\n        for qidx in qidxs:\n            # each minsize is <= than the last, yielding new room opportunities\n            pref, minsize = queries[qidx]\n            while r < len(rooms) and rooms[r][1] >= minsize:\n                avail.add(rooms[r][0])\n                r += 1\n\n            if not avail: continue # leave answer as -1\n\n            # avail now has all rooms with suitable size\n            i = avail.bisect_left(pref)\n            if i == len(avail):\n                ans[qidx] = avail[-1]\n            else:\n                id = avail[i] # first id >= pref\n                if i:\n                    # there is a lesser id as well\n                    lower = avail[i-1]\n                    if pref-lower <= id-pref:\n                        # if lower is closer: take lower\n                        # if lower is same distane: take lower as tie-breaker\n                        #    hence <= to cover both cases\n                        id = lower\n\n                ans[qidx] = id\n\n        return ans\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n        # print(f"{rooms=}")\n        # print(f"{queries=}")\n\n        # def answer(pref, minsize) -> int:\n        #     """Returns room index with size at least minsize closest to pref"""\n\n        #     if minsize > M: return -1 # no such room has this size\n        #     if pref >= M: return M_idx # earliest room index with max size, the closest to pref >= M\n\n        #     # start of room range with suitable sizes\n        #     lo = bisect_left(rooms, minsize, key=lambda room: room[1])\n\n        #     # index of room with closest size >= pref\n        #     i = bisect_left(rooms, pref, key=lambda room: room[1], lo=lo)\n        #     nxt_size = rooms[i][1]\n        #     if i > lo:\n        #         prev_size = rooms[i-1][1]\n        #         if pref-prev_size < nxt_size-pref:\n        #             # answer is min room index with prior size\n        #             i = bisect_left(rooms, prev_size, key=lambda room: room[1], hi=i)\n        #             return rooms[i][0]\n        #         elif pref-prev_size == nxt_size-pref:\n        #             # prior size is tied, return minimum earliest number\n        #             j = bisect_left(rooms, prev_size, key=lambda room: room[1], hi=i)\n        #             return min(rooms[i][0], rooms[j][0])\n                \n        #         # else: nxt_size is closer\n        #         return rooms[i][0]\n        #     else:\n        #         # no valid room with < pref\n        #         return rooms[i][0]\n\n        # return list(answer(*query) for query in queries)\n```
['Python3']