1847. Closest Room

1847. Closest Room

There is a hotel with n rooms. The rooms are represented by a 2D integer array rooms where rooms[i] = [roomIdi, sizei]
denotes that there is a room with room number 
roomIdi and size equal to sizei. Each roomIdi is guaranteed to be unique.

You are also given k queries in a 2D array queries where queries[j] = [preferredj, minSizej]. The answer to the jth 
query is the room number id of a room such that:

The room has a size of at least minSizej, and
abs(id - preferredj) is minimized, where abs(x) is the absolute value of x.
If there is a tie in the absolute difference, then use the room with the smallest such id. If there is no such room, 
the answer is -1.

Return an array answer of length k where answer[j] contains the answer to the jth query.

 

Example 1:

Input: rooms = [[2,2],[1,2],[3,2]], queries = [[3,1],[3,3],[5,2]]
Output: [3,-1,3]
Explanation: The answers to the queries are as follows:
Query = [3,1]: Room number 3 is the closest as abs(3 - 3) = 0, and its size of 2 is at least 1. The answer is 3.
Query = [3,3]: There are no rooms with a size of at least 3, so the answer is -1.
Query = [5,2]: Room number 3 is the closest as abs(3 - 5) = 2, and its size of 2 is at least 2. The answer is 3.
Example 2:

Input: rooms = [[1,4],[2,3],[3,5],[4,1],[5,2]], queries = [[2,3],[2,4],[2,5]]
Output: [2,1,3]
Explanation: The answers to the queries are as follows:
Query = [2,3]: Room number 2 is the closest as abs(2 - 2) = 0, and its size of 3 is at least 3. The answer is 2.
Query = [2,4]: Room numbers 1 and 3 both have sizes of at least 4. The answer is 1 since it is smaller.
Query = [2,5]: Room number 3 is the only room with a size of at least 5. The answer is 3.
 

Constraints:

n == rooms.length
1 <= n <= 105
k == queries.length
1 <= k <= 104
1 <= roomIdi, preferredj <= 107
1 <= sizei, minSizej <= 107

难度 : Hard

思路

Note m = rooms.length, n = queries.length

• brute force 解法是对每个query扫描整个room找到满足条件的最close的room id.
  时间复杂度是 O(m*n) 最大10^9 会超时
• Binary Search, 先对rooms进行排序，size大的排前面。然后每个query数组添加一个id，然后对query按照size进行逆序排序
  先处理size最大的query，那么得到的可能room 后面的query也会用到。把得到的candidate放在TreeSet 里就可以按照id进行binary search
  空间复杂度 O(m + n) 因为使用了一个新的一个数组来保存queries with index
  时间复杂度 O(m log(m) + n log(n) + m log(n) + m log (m))
  最后的 m * log (m) 是因为把candidate插入到TreeSet需要的时间

class Solution {
    public int[] closestRoom(int[][] rooms, int[][] queries) {
        Arrays.sort(rooms, Comparator.comparingInt(x -> -x[1]));
        int m = rooms.length;
        int n = queries.length;
        int[][] queriesNew = new int[n][];
        for (int i = 0; i < n; i++) {
            queriesNew[i] =new int[]{ queries[i][0],queries[i][1],i};
        }
        Arrays.sort(queriesNew, Comparator.comparingInt(x -> -x[1]));
        //candidates
        TreeSet<Integer> candidates = new TreeSet<>();
        //j is the current index of room
        int j = 0;
        int[] ans = new int[n];
        //by default ans[i] = -1
        Arrays.fill(ans, -1);
        for (int i = 0; i < n; i++) {
            //here,we only scan the rooms once, so it's efficient
            while (j < m && rooms[j][1] >= queriesNew[i][1]) {
                candidates.add(rooms[j][0]);
                j++;
            }
            if (candidates.isEmpty()) {
                continue;
            }
            int id = queriesNew[i][0];
            //binary search to find the closest id
            Integer floor = candidates.floor(id);
            Integer ceiling = candidates.ceiling(id);
            floor = floor == null ? Integer.MIN_VALUE : floor;
            ceiling = ceiling == null ? Integer.MAX_VALUE : ceiling;
            if (Math.abs(floor - id) <= Math.abs(ceiling - id)) {
                ans[queriesNew[i][2]] = floor;
            } else {
                ans[queriesNew[i][2]] = ceiling;
            }
        }
        return ans;
    }
}