[Java/Python] Sorting queries by their minSize - Clean & Concise
Idea\n- We sort queries by the decreasing of its minSize order.\n- We sort rooms by the decreasing of its size order.\n- We initialize roomIdsSoFar TreeSet, thi
**Idea**\n- We sort `queries` by the decreasing of its `minSize` order.\n- We sort `rooms` by the decreasing of its `size` order.\n- We initialize `roomIdsSoFar` TreeSet, this includes all room ids which have `size` >=` minSize` of current query so far.\n- For each query `q` in `queries`:\n\t- Add all room ids which have `size` >=` minSize` of current query.\n\t- Query `floor` and `ceiling` of `q[0]` (preferredId) from `roomIdsSoFar` to pick the id which closest to our `preferredId`\n\n**Complexity**\n- Time: `O(NlogN + KlogK  + K*logN)`\n- Space: `O(N + K)`\n\n**Java**\n- Using `TreeSet` structure which we can query `floor` and `ceiling` in `O(logN)`\n```java\nclass Solution {\n    public int[] closestRoom(int[][] rooms, int[][] queries) {\n        int n = rooms.length, k = queries.length;\n        Integer[] indexes = new Integer[k];\n        for (int i = 0; i < k; i++) indexes[i] = i;\n        Arrays.sort(rooms, (a, b) -> Integer.compare(b[1], a[1])); //Sort by decreasing order of room size\n        Arrays.sort(indexes, (a, b) -> Integer.compare(queries[b][1], queries[a][1])); // Sort by decreasing order of query minSize\n        TreeSet<Integer> roomIdsSoFar = new TreeSet<>();\n        int[] ans = new int[k];\n        int i = 0;\n        for (int index : indexes) {\n            while (i < n && rooms[i][1] >= queries[index][1]) { // Add id of the room which its size >= query minSize\n                roomIdsSoFar.add(rooms[i++][0]);\n            }\n            ans[index] = searchClosetRoomId(roomIdsSoFar, queries[index][0]);\n        }\n        return ans;\n    }\n    int searchClosetRoomId(TreeSet<Integer> treeSet, int preferredId) {\n        Integer floor = treeSet.floor(preferredId);\n        Integer ceiling = treeSet.ceiling(preferredId);\n        int ansAbs = Integer.MAX_VALUE, ans = -1;\n        if (floor != null) {\n            ans = floor;\n            ansAbs = Math.abs(preferredId - floor);\n        }\n        if (ceiling != null && ansAbs > Math.abs(preferredId - ceiling)) {\n            ans = ceiling;\n        }\n        return ans;\n    }\n}\n```\n\n\n**Python 3 - Using SortedList from sortedcontainers  library**\n- For Map/TreeMap structure, we can use [sortedcontainers](http://www.grantjenks.com/docs/sortedcontainers/) which is imported by Leetcode.\n```python\nfrom sortedcontainers import SortedList\n\nclass Solution:\n    def closestRoom(self, rooms: List[List[int]], queries: List[List[int]]) -> List[int]:\n        rooms.sort(key=lambda x: x[1], reverse=True)  # Sort by decreasing order of room size\n        qArr = [[i, q] for i, q in enumerate(queries)]  # Zip queries with their index\n        qArr.sort(key=lambda x: x[1][1], reverse=True)  # Sort by decreasing order of query minSize\n\n        def searchClosestRoomId(preferredId):\n            if len(roomIdsSoFar) == 0: \n                return -1\n            cands = []\n            i = roomIdsSoFar.bisect_right(preferredId)\n            if i > 0: \n                cands.append(roomIdsSoFar[i - 1])\n            if i < len(roomIdsSoFar): \n                cands.append(roomIdsSoFar[i])\n            return min(cands, key=lambda x: abs(x - preferredId))\n\n        roomIdsSoFar = SortedList()\n        n, k = len(rooms), len(queries)\n        i = 0\n        ans = [-1] * k\n        for index, (prefferedId, minSize) in qArr:\n            while i < n and rooms[i][1] >= minSize:\n                roomIdsSoFar.add(rooms[i][0])  # Add id of the room which its size >= query minSize\n                i += 1\n            ans[index] = searchClosestRoomId(prefferedId)\n        return ans\n```\n\n\n**Python 3 - Using bisect.insort(arr, x)**\n- We can use `bisect.insort` which will insert an element into an array very fast, it has time complextity `O(N)` but it runs too fast, which we can treat it as `O(logN)`.\n```python\nclass Solution:\n    def closestRoom(self, rooms: List[List[int]], queries: List[List[int]]) -> List[int]:\n        rooms.sort(key=lambda x: x[1], reverse=True)  # Sort by decreasing order of room size\n        qArr = [[i, q] for i, q in enumerate(queries)]  # Zip queries with their index\n        qArr.sort(key=lambda x: x[1][1], reverse=True)  # Sort by decreasing order of query minSize\n\n        def searchClosestRoomId(preferredId):\n            if len(roomIdsSoFar) == 0:\n                return -1\n            cands = []\n            i = bisect_right(roomIdsSoFar, preferredId)\n            if i > 0:\n                cands.append(roomIdsSoFar[i - 1])\n            if i < len(roomIdsSoFar):\n                cands.append(roomIdsSoFar[i])\n            return min(cands, key=lambda x: abs(x - preferredId))\n\n        roomIdsSoFar = []  # Room id is sorted in increasing order\n        n, k = len(rooms), len(queries)\n        i = 0\n        ans = [-1] * k\n        for index, (prefferedId, minSize) in qArr:\n            while i < n and rooms[i][1] >= minSize:\n                bisect.insort(roomIdsSoFar, rooms[i][0])  # Add id of the room which its size >= query minSize\n                i += 1\n            ans[index] = searchClosestRoomId(prefferedId)\n        return ans\n```
[]