[Python] Sorted List solution, explained
The idea of this problem is to sort our rooms and queries by time and start with biggest times and keep sorted list aval for avaliable rooms: such that we can c
The idea of this problem is to sort our rooms and queries by time and start with biggest times and keep sorted list `aval` for avaliable rooms: such that we can choose from. Imagine, that we have rooms with sizes `[7, 6, 3, 2, 1]` and queries with sizes `[5, 3, 1]`. Then on the first step we see query with size `5` and avaliable rooms we have are `[7, 6]`. Then we look at query `3` and now we have avaliable rooms `[7, 6, 3]`. Finally, we look at query `1` and now avaliable rooms are `[7, 6, 3, 2, 1]`.\n\nHowever we need to return closest index among all avaliable rooms, so we need to keep our avaliable rooms sorted with `id`. If fact, we put tuple `(id, size)` into our sorted list. \n\nAlso we use two pointers approach: `p1` is responsible for rooms `R` and `p2` is responsible for queries `Q`. If `R[p1][0] >= Q[p2][0]`, it means that we can add one more room to `aval`, so we do it and update `p1`. If we can not do it, it means we already saturated `aval`, so we look at it. If it is empty, we must return `-1`, we do not have any candidates. If it is not empty, we use binary search: there can be at most `3` (in fact `2`) candidates for the nearest index: we chose the best of them.\n\n#### Complexity\nLet `n` be number of rooms and `q` is number of queries. Then we have time complexity `O(n log n + q log n)` to sort our data and then we have `n+q` iterations in our 2 pointers approach, where each time we use either `add` or `bisect` operation with complexity `O(log n)`. So, total time complexity is `O(n log n + q log q + q log n)`. Space complexity is `O(n + q)`.\n\n#### Code\n```python\nfrom sortedcontainers import SortedList\n\nclass Solution:\n    def closestRoom(self, rooms, queries):\n        Q = sorted([(y, x, i) for i, (x,y) in enumerate(queries)])[::-1]\n        R = sorted((y, x) for x, y in rooms)[::-1]\n        n, q = len(R), len(Q)\n        p1, p2, aval, ans = 0, 0, SortedList(), [-1]*q\n\n        while p1 <= n and p2 < q:\n            if p1 < n and R[p1][0] >= Q[p2][0]:\n                aval.add(R[p1][1])\n                p1 += 1\n            else:\n                if len(aval) != 0:\n                    preferred, ind = Q[p2][1], Q[p2][2]\n                    i = aval.bisect(preferred)\n                    \n                    cands = []\n                    if i > 0: cands.append(aval[i-1])\n                    if i < len(aval): cands.append(aval[i])\n                    ans[ind] = min(cands, key = lambda x: abs(x - preferred))\n\n                p2 += 1\n\n        return ans\n```\n\nIf you have any questions, feel free to ask. If you like solution and explanations, please **Upvote!**
[]