包含每个查询的最小区间【LC1851】
给你一个二维整数数组
intervals，其中intervals[i] = [lefti, righti]表示第i个区间开始于lefti、结束于righti（包含两侧取值，闭区间）。区间的 长度 定义为区间中包含的整数数目，更正式地表达是righti - lefti + 1。再给你一个整数数组
queries。第j个查询的答案是满足lefti <= queries[j] <= righti的 长度最小区间i的长度 。如果不存在这样的区间，那么答案是-1。以数组形式返回对应查询的所有答案。
排序+离线查询+小顶堆
- 思路
- 我们需要找到包含
queries[j]的区间的最小长度，而查询的顺序不会影响结果，因此可以采用离线查询的思路，按照某种顺序处理每个查询，以便于不需要重复访问区间，减少时间复杂度
什么顺序？
- 按照
queries[j]从小到大的顺序处理查询，为了找到所有包含queries[j]的区间，因此需要对所有区间按照左端点从小到大的顺序进行排序 - 使用小顶堆存放区间信息，小顶堆以区间长度从小到大排序。
- 对于每个查询，将可能包含该值的所有区间入堆，即如果该区间左端点小于等于
queries[j]，那么将其放入小顶堆中
- 怎么获得最小区间长度？
将所有可能区间放入后，进行判断：
- 如果堆顶元素右端点小于
queries[j]，那么该区间不包含queries[j]，将其弹出 - 如果堆不为空，那么堆顶元素即为查询结果；否则，不存在合法区间，答案为-1
- 实现
class Solution { public int[] minInterval(int[][] intervals, int[] queries) { int n = intervals.length, m = queries.length; int[] res = new int[m]; int[][] q = new int[m][2]; for (int i = 0; i < m; i++){ q[i][0] = queries[i]; q[i][1] = i; } Arrays.sort(q, (o1, o2) -> o1[0] - o2[0]);// 对查询从小到大排序 Arrays.sort(intervals, (o1, o2) -> o1[0] - o2[0]);// 对intervals左端点从小到大排序 int i = 0; PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> o1[2] - o2[2]);// 小顶堆，按照区间长度从小到大排序 for (int j = 0; j < m; j++){ int val = q[j][0], index = q[j][1]; while (i < n && intervals[i][0] <= val){ pq.add(new int[]{intervals[i][0], intervals[i][1], intervals[i][1] - intervals[i][0] + 1});// 将可能包含该值的所有区间入堆 i++; } while (!pq.isEmpty() && pq.peek()[1] < val){ pq.poll();// 将不包含该值的所有区间入堆 } if (pq.isEmpty()){ res[index] = -1; }else{ res[index] = pq.peek()[2]; } } return res; } }
