查询每个点的最小覆盖区间如何离线排序加小根堆？

简化版

查询每个点的最小覆盖区间，可以把区间按左端点排序，查询点按值排序。扫描查询点 q 时，把所有 left <= q 的区间加入小根堆，堆按区间长度排序；再弹出所有 right < q 的过期区间，堆顶就是覆盖 q 的最短区间。

详细版

这是典型离线查询。排序后每个区间只入堆一次，每个过期区间只出堆一次。堆元素保存 (长度, right)，因为排序保证入堆区间左端已经不大于当前查询点，只需要检查右端是否还覆盖。

要保留查询原下标，最终答案放回原顺序。时间复杂度 O((n+m)log n)，空间复杂度 O(n+m)。

完整版教学

一、为什么直接逐个查询会慢

如果每个查询点都遍历所有区间，复杂度是 O(nm)。当区间和查询都很多时会超时。问题需要复用“已经按位置扫描过”的信息。

区间数 n = 100000
查询数 m = 100000
暴力 n*m = 10^10

离线排序可以把多个查询放到同一条扫描线上处理。

二、为什么查询点要排序

按查询点从小到大处理时，区间是否满足 left <= q 具有单调性。一个区间一旦左端点不大于当前查询点，就会对当前和后续更大的查询点有机会生效。

条件	随 q 增大变化
`left <= q`	一旦满足，之后一直满足
`right >= q`	可能从满足变成过期

记忆钩子：离线扫描把“反复找候选”变成“候选逐步入堆、过期逐步出堆”。

这就是排序查询的价值。

三、堆里放什么

对当前查询点 q，所有左端点 <=q 的区间都入堆。堆按区间长度排序：

length = right - left + 1

堆元素至少要包含：

(length, right)

因为左端点已经通过入堆条件保证，是否仍覆盖当前点只需要看 right >= q。

四、为什么要弹出过期区间

堆顶可能是最短区间，但它的右端点已经小于当前查询点，就不再覆盖 q，必须弹出。

q = 8
堆顶区间 [1,5]，长度 5
right=5 < 8，已经过期

一直弹到堆为空或堆顶 right >= q。此时堆顶才是所有候选中的最短有效区间。

五、代码模板

int[] minInterval(int[][] intervals, int[] queries) {
    Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));
    int m = queries.length;
    int[][] qs = new int[m][2];
    for (int i = 0; i < m; i++) {
        qs[i][0] = queries[i];
        qs[i][1] = i;
    }
    Arrays.sort(qs, Comparator.comparingInt(a -> a[0]));
    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
    int[] ans = new int[m];
    Arrays.fill(ans, -1);
    int i = 0;
    for (int[] qu : qs) {
        int q = qu[0];
        while (i < intervals.length && intervals[i][0] <= q) {
            int l = intervals[i][0], r = intervals[i][1];
            pq.offer(new int[]{r - l + 1, r});
            i++;
        }
        while (!pq.isEmpty() && pq.peek()[1] < q) pq.poll();
        if (!pq.isEmpty()) ans[qu[1]] = pq.peek()[0];
    }
    return ans;
}

注意查询排序后必须保存原下标，否则答案顺序会乱。

六、用例子推演

区间：

[1,4], [2,4], [3,6], [4,4]
queries = [2,3,4,5]

处理 q=4 时，所有左端点 <=4 的区间都已入堆，堆中最短有效区间是 [4,4]，长度 1。处理 q=5 时 [4,4] 过期，会被弹出，剩下 [3,6] 长度 4 可用。

这说明“最短”必须和“仍覆盖当前点”一起判断。

七、常见误区与追问

误区：堆顶最短就直接返回。 堆顶可能右端点已过期，必须先弹出。
误区：查询排序后忘记原下标。 输出必须恢复原查询顺序。
误区：把所有区间一开始都入堆。 这样还要检查左端点，失去扫描线单调性。
追问：为什么堆里不用存 left？ 入堆时已经保证 left <= q，后续查询更大也仍满足。
追问：复杂度是多少？ 排序加堆操作，总体 O((n+m)log n)。
追问：这是在线算法吗？ 不是，它依赖提前知道所有查询并排序，是离线查询。

八、加强记忆

最小覆盖区间查询记成“区间按左端进场，按右端退场，堆顶管最短”。查询点排序后，左端满足条件的区间只会越来越多；右端过期的区间从堆里弹掉。保留查询原下标，是离线题最后一步的命门。

简化版

详细版