[Java] Sort by roomId, two passes (ascending/descending roomId)
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \nTraverse rooms by ascen
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nTraverse rooms by ascending id maintaining a queue of active queries:\n- add queries as its preferred room is passed\n- prioritize active queries by smallest minSize\n- resolve active queries if the current room is large enough\n\nRepeat in the opposite direction and select better result for each query.\n \n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO(N_rooms log(N_rooms) + N_queries log(N_queries))\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(N_queries)\n# Code\n```\nclass Solution {\n    public int[] closestRoom(int[][] rooms, int[][] queries) {\n        // all rooms sorted by ascending roomId\n        Arrays.sort(rooms,(r1,r2) -> Integer.compare(r1[0],r2[0]));\n        int[][] oq = new int[queries.length][3];\n        for (int i = 0; i < queries.length; i++) {\n            oq[i][0] = i;\n            oq[i][1] = queries[i][0];\n            oq[i][2] = queries[i][1];\n        }\n        // active queries sorted by ascending minSize\n        PriorityQueue<int[]> aq = new PriorityQueue<int[]>((q1,q2) -> Integer.compare(q1[2],q2[2]));\n\n        // all queries sorted by ascending preferred\n        Arrays.sort(oq,(q1,q2) -> Integer.compare(q1[1],q2[1]));\n\n        int[] ra = new int[queries.length];\n        int nq = 0;\n        // iterate over rooms by ascending roomId\n        for (int i = 0; i < rooms.length; i++) {\n            // activate queries if preferred room has been reached (or passed) \n            while (nq < oq.length && oq[nq][1] <= rooms[i][0]) {\n                aq.add(oq[nq++]);\n            }\n            // resolve active queries if current room is big enough\n            while (!aq.isEmpty() && aq.peek()[2] <= rooms[i][1]) {\n                ra[aq.poll()[0]] = i+1;\n            }\n        }\n\n        // repeat going the opposite direction (rooms & queries)\n        aq.clear();\n        int[] rd = new int[queries.length];\n        nq = oq.length-1;\n        for (int i = rooms.length-1; i >= 0; i--) {\n            while (nq >= 0 && oq[nq][1] >= rooms[i][0]) {\n                aq.add(oq[nq--]);\n            }\n            while (!aq.isEmpty() && aq.peek()[2] <= rooms[i][1]) {\n                rd[aq.poll()[0]] = i+1;\n            }\n        }\n\n        // combine results from ascending & descending passes\n        for (int i = 0; i < queries.length; i++) {\n            if (rd[i] == 0 && ra[i] == 0) {\n                ra[i] = -1;\n                continue;\n            }\n            if (rd[i] == 0 ) {\n                ra[i] = rooms[ra[i]-1][0];\n                continue;\n            }\n            if (ra[i] == 0) {\n                ra[i] = rooms[rd[i]-1][0];\n                continue;\n            }\n            if (rooms[ra[i]-1][0] - queries[i][0] < queries[i][0] - rooms[rd[i]-1][0]) ra[i] = rooms[ra[i]-1][0];\n            else ra[i] = rooms[rd[i]-1][0];\n        }\n        return ra;\n    }\n}\n```
['Java']