1837.最近的房间

思路

这题一开始我只想到了把rooms数组排序，但是没有想到实际上还可以对查询数组进行排序。这是一种离线的做法，因为我们已经知道了所有的输入数据，就不用像数据是在线的那样受到限制，可以自由地处理输入数据。

看到这一点后，我也想到了将查询数组和rooms数组都按minSize排序，我们就可以在查询时维护这样一个性质：后面的查询范围包括了前面的查询范围，并且查询范围是从0逐步递增到rooms长度的。也就是我们可以对两个数组分别用一个指针来表示这个子范围。

当时想到这里就卡住了，没有想到如何在logn的时间内对无序的子范围内roomID进行查询。

其实，在数组中这的确是无序的，但是我们可以把它提取到一个有序的数据结构中！我们可以把子范围中的roomId再提出来到一个TreeSet中（红黑树），这样就可以用树维护logn时间的查询，这样问题就迎刃而解了。

关键点：离线，将子规模数据放入另一个数据结构中，TreeSet

细节

1. Java中如何自定义数组排序？

在Arrays.sort中传入lambda表达式比较函数，其接收两个待比较元素，返回一个整数，大于0则前者大。

Arrays.sort(rooms, (a, b) -> (a[1] - b[1]));

2.离线处理时遇到需要按序返回怎么办？

朴素的想法是再开一个相同的数据结构，并补上序号这个标签，但是这样空间复杂度过高。

实际上我们只需要再开一个标签数组，并对这个标签数组排序即可。

Integer qs[] = new Integer [m];//sort的lambda表达式需要一个对象类型
Arrays.setAll(qs, i -> i);//快速初始化
Arrays.sort(qs, (a, b) -> (queries[b][1] - queries[a][1]));

这题收获满满，是非常好的一道题。

代码

class Solution {
    public int[] closestRoom(int[][] rooms, int[][] queries) {
        int n = rooms.length;
        int m = queries.length;
        Integer qs[] = new Integer [m];
        Arrays.setAll(qs, i -> i);
        Arrays.sort(rooms, (a, b) -> (a[1] - b[1]));
        Arrays.sort(qs, (a, b) -> (queries[b][1] - queries[a][1]));
        TreeSet<Integer> ts = new TreeSet<>();
        int i = n - 1;
        int minv = Integer.MAX_VALUE;
        int ans[] = new int[m];
        for (int j : qs) {
            int pref = queries[j][0]; 
            int ms = queries[j][1];
            while (i >= 0 && rooms[i][1] >= ms) {
                ts.add(rooms[i][0]);
                i--;
            }
            Integer c = ts.ceiling(pref);
            Integer f = ts.floor(pref);
            if (c == null && f == null) ans[j] = -1;
            else if (f == null) ans[j] = c;
            else if (c == null) ans[j] = f;
            else {
                if (c - pref >= pref - f) ans[j] = f;
                else ans[j] = c;
            }
        }
        return ans;
    }
}