1851. 包含每个查询的最小区间 扫描线/优先队列

1851. 包含每个查询的最小区间

给你一个二维整数数组 intervals ，其中 intervals[i] = [lefti, righti] 表示第 i 个区间开始于 lefti 、结束于 righti（包含两侧取值，闭区间）。区间的 长度 定义为区间中包含的整数数目，更正式地表达是 righti - lefti + 1 。

再给你一个整数数组 queries 。第 j 个查询的答案是满足 lefti <= queries[j] <= righti 的 长度最小区间 i 的长度 。如果不存在这样的区间，那么答案是 -1 。

以数组形式返回对应查询的所有答案。

示例 1：

输入：intervals = [[1,4],[2,4],[3,6],[4,4]], queries = [2,3,4,5]
输出：[3,3,1,4]
解释：查询处理如下：
- Query = 2 ：区间 [2,4] 是包含 2 的最小区间，答案为 4 - 2 + 1 = 3 。
- Query = 3 ：区间 [2,4] 是包含 3 的最小区间，答案为 4 - 2 + 1 = 3 。
- Query = 4 ：区间 [4,4] 是包含 4 的最小区间，答案为 4 - 4 + 1 = 1 。
- Query = 5 ：区间 [3,6] 是包含 5 的最小区间，答案为 6 - 3 + 1 = 4 。

示例 2：

输入：intervals = [[2,3],[2,5],[1,8],[20,25]], queries = [2,19,5,22]
输出：[2,-1,4,6]
解释：查询处理如下：
- Query = 2 ：区间 [2,3] 是包含 2 的最小区间，答案为 3 - 2 + 1 = 2 。
- Query = 19：不存在包含 19 的区间，答案为 -1 。
- Query = 5 ：区间 [2,5] 是包含 5 的最小区间，答案为 5 - 2 + 1 = 4 。
- Query = 22：区间 [20,25] 是包含 22 的最小区间，答案为 25 - 20 + 1 = 6 。

提示：

• 1 <= intervals.length <= 1e5
• 1 <= queries.length <= 1e5
• queries[i].length == 2
• 1 <= lefti <= righti <= 1e7
• 1 <= queries[j] <= 1e7

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/minimum-interval-to-include-each-query
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

做题结果

扫描线还是写不出来，优先队列 看了扫描线的答案以后写了出来

方法1：扫描线

1. 分为两个状态，左端点和右端点，按照点的位置从左到右排序

2.桶一个点左端点排右端点前面

3.在当前点钱或者当前的的左端点累计长度

3.拿最大长度作为返回长度

class Solution {
    public int[] minInterval(int[][] intervals, int[] queries) {
        List<int[]> ranges = new ArrayList<>();
        for(int[] interval:intervals){
            ranges.add(new int[]{0,interval[0],interval[1]-interval[0]+1});
            ranges.add(new int[]{1,interval[1],interval[1]-interval[0]+1});
        }
 
        ranges.sort((a,b)->a[1]==b[1]?a[0]-b[0]:a[1]-b[1]);
        int m = queries.length;
        Integer[] sortQ = new Integer[m];
        for(int i = 0; i < m; i++) sortQ[i] = i;
        Arrays.sort(sortQ,(a,b)->queries[a]-queries[b]);
        int[] ans = new int[m];
        int preI = -1;
        TreeMap cnts = new TreeMap<>();
        int j = 0;
        for(int i:sortQ){
            if(preI!=-1 && queries[i]==queries[preI]){
                ans[i] = ans[preI];
                continue;
            }
            while (j1]1]==queries[i]&&ranges.get(j)[0]==0)){
                int len = ranges.get(j)[2];
                if(ranges.get(j)[0]==0) cnts.put(len,cnts.getOrDefault(len,0)+1);
                else {
                    cnts.put(len,cnts.getOrDefault(len,0)-1);
                    if(cnts.get(len)==0) cnts.remove(len);
                }
                ++j;
            }
            ans[i]=cnts.isEmpty()?-1:cnts.firstKey();
            preI = i;
        }
        return ans;
    }
}

方法2：优先队列

使用懒删除策略

1. 遇到左端点添加索引到优先队列（优先队列按照长度从小到达排序）

2. 如果堆顶索引的结束位置在当前之前进行移除（懒删除）

3. 取堆顶长度

  class Solution {
    public int[] minInterval(int[][] intervals, int[] queries) {
        Arrays.sort(intervals,(a,b)->a[0]-b[0]);//先按起点排序
        int n = intervals.length;
        int m = queries.length;
        Integer[] sortQ = new Integer[m];
        for(int i = 0; i < m; i++) sortQ[i] = i;
        Arrays.sort(sortQ,(a,b)->queries[a]-queries[b]);
        int[] ans = new int[m];
        PriorityQueue pq = new PriorityQueue<>((a,b)->(intervals[a][1]-intervals[a][0])-(intervals[b][1]-intervals[b][0]));
        int j = 0;
        for(int i:sortQ){
            while (j0]<=queries[i]){
                pq.offer(j);
                j++;
            }
 
            while (!pq.isEmpty()&&intervals[pq.peek()][1]
            ans[i] = pq.isEmpty()?-1:intervals[pq.peek()][1]-intervals[pq.peek()][0]+1;
        }
        return ans;
    }
}