1851. 包含每个查询的最小区间 (opens new window)

1.优先队列+区间排序

预处理阶段先进行三个排序：

• intervals按照左边界从小到大进行排序
• queries按照从小到大进行排序。返回最终结果集需要按照原先查询顺序，因此开辟二维数组保存原先下标。
• 创建一个优先级队列，排序规则按照区间大小进行排序。

对于每一个查询要想找到最小区间，要满足三步①左边界小于当前值②右边界大于当前值③区间最小。操作如下：

1. 首先将所有左边界小于等于当前查询值的区间加入队列。相当于找到所有满足①条件的区间。这里区间已经排过序，因此直接按照index顺序入队。
2. 将队列中所有右边界小于当前查询值的区间移出。相当于过滤掉不满足②条件的区间。这里查询值排过序，因此出队区间肯定小于后续查询值，所以移除后不会影响后续查询值。
3. 区间放在优先级队列进行操作，因此天然满足条件③。队首元素区间大小即为当前查询结果。

在上面三个排序性的约束下，入队的元素都有可能成为当前和后续查询的结果，而出队的元素一定不可能成为当前和后续查询的结果。故整个查询过程时间复杂度O(intervals.length)。

总结：【1】区间问题除了区间大小以外，还可以考虑按照左右边界排序的思路解题。

【2】在线查询复杂度比较高，可使用“离线查询”。本质上就是改变批量数据的查询顺序，将结果原序返回。

• 在线查询：每次获得一个请求，查询一次并直接放回结果。
• 离线查询：通过改变和处理原本查询的顺序，批量/顺序处理完所有数据之后，再将结果按照绑定的原先查询顺序返回。

class Solution {
    public int[] minInterval(int[][] intervals, int[] queries) {
        int[] res=new int[queries.length];
        int[][] que=new int[queries.length][2];
        for(int i=0;i<queries.length;i++){
            que[i][0]=queries[i];
            que[i][1]=i;
        }
        //对intervals排序
        Arrays.sort(intervals,new Comparator<int[]>(){
            public int compare(int[] o1,int[] o2){
                return o1[0]-o2[0];
            }
        });
        //对que进行排序
        Arrays.sort(que,new Comparator<int[]>(){
            public int compare(int[] o1,int[] o2){
                return o1[0]-o2[0];
            }
        });
        //优先级队列
        PriorityQueue<int[]> queue=new PriorityQueue<>(new Comparator<int[]>(){
            public int compare(int[] o1,int[] o2){
                return o1[1]-o1[0]-(o2[1]-o2[0]);
            }
        });
        int inx=0;
        for(int i=0;i<que.length;i++){
            //入队：所有区间【a,b】的左边界a只要小于等于当前查询que【i】，则入栈
            while(inx<intervals.length&&intervals[inx][0]<=que[i][0]){
                queue.offer(intervals[inx]);
                inx++;
            }
            //出队：所有区间【a,b】的右边界b只要小于当前查询que【i】，则入栈
            while(queue.size()>0&&queue.peek()[1]<que[i][0]){
                queue.poll();
            }
            if(queue.size()>0) res[que[i][1]]=queue.peek()[1]-queue.peek()[0]+1;
            else res[que[i][1]]=-1;
        }
        return res;
    }
}