You are given a 2D integer array intervals
, where intervals[i] = [lefti, righti]
describes the ith
interval starting at lefti
and ending at righti
(inclusive). The size of an interval is defined as the number of integers it contains, or more formally righti - lefti + 1
.
You are also given an integer array queries
. The answer to the jth
query is the size of the smallest interval i
such that lefti <= queries[j] <= righti
. If no such interval exists, the answer is -1
.
Return an array containing the answers to the queries.
Example 1:
Input: intervals = [[1,4],[2,4],[3,6],[4,4]], queries = [2,3,4,5] Output: [3,3,1,4] Explanation: The queries are processed as follows: - Query = 2: The interval [2,4] is the smallest interval containing 2. The answer is 4 - 2 + 1 = 3. - Query = 3: The interval [2,4] is the smallest interval containing 3. The answer is 4 - 2 + 1 = 3. - Query = 4: The interval [4,4] is the smallest interval containing 4. The answer is 4 - 4 + 1 = 1. - Query = 5: The interval [3,6] is the smallest interval containing 5. The answer is 6 - 3 + 1 = 4.
Example 2:
Input: intervals = [[2,3],[2,5],[1,8],[20,25]], queries = [2,19,5,22] Output: [2,-1,4,6] Explanation: The queries are processed as follows: - Query = 2: The interval [2,3] is the smallest interval containing 2. The answer is 3 - 2 + 1 = 2. - Query = 19: None of the intervals contain 19. The answer is -1. - Query = 5: The interval [2,5] is the smallest interval containing 5. The answer is 5 - 2 + 1 = 4. - Query = 22: The interval [20,25] is the smallest interval containing 22. The answer is 25 - 20 + 1 = 6.
Constraints:
1 <= intervals.length <= 105
1 <= queries.length <= 105
intervals[i].length == 2
1 <= lefti <= righti <= 107
1 <= queries[j] <= 107
包含每个查询的最小区间。
给你一个二维整数数组 intervals ,其中 intervals[i] = [lefti, righti] 表示第 i 个区间开始于 lefti 、结束于 righti(包含两侧取值,闭区间)。区间的 长度 定义为区间中包含的整数数目,更正式地表达是 righti - lefti + 1 。
再给你一个整数数组 queries 。第 j 个查询的答案是满足 lefti <= queries[j] <= righti 的 长度最小区间 i 的长度 。如果不存在这样的区间,那么答案是 -1 。
以数组形式返回对应查询的所有答案。
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/minimum-interval-to-include-each-query
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
思路是扫描线。感觉思路不难但是实现起来有很多细节需要注意。
首先我们要将 intervals 按 start 排序,同时将 queries 和他们各自的 index 包装成一个二维数组且按照 queryVal 排序。再来我们需要一个最小堆存储所有的 intervals,这个堆按 interval 的宽度(end - start)排序。
接下来我们开始遍历 queries,对于每个 queryVal,我们将所有 start <= queryVal 的 interval 都放入最小堆。然后我们从最小堆中弹出所有 end < queryVal 的元素,因为这些 interval 虽然 start < queryVal 但是 end 也小于,等于是 queryVal 不能被这些 intervals 包含,所以要舍弃。此时如果最小堆里还有 intervals,当前的 queryVal 则是能落在这些 intervals 中间的。此时我们再从最小堆中弹出堆顶元素,这个元素就是既能 cover 住 queryVal,且又是宽度最小的那个。
时间O(n * nlogn) - 要处理 n 个 queryVal,对于每个 queryVal,我们都需要将所有 intervals 放入最小堆过滤一遍
空间O(n)
Java实现
1 class Solution { 2 public int[] minInterval(int[][] intervals, int[] queries) { 3 int n = queries.length; 4 int[][] queriesWithIndex = new int[n][2]; 5 for (int i = 0; i < n; i++) { 6 queriesWithIndex[i] = new int[] { queries[i], i }; 7 } 8 9 // 区间按start排序 10 Arrays.sort(intervals, (a, b) -> a[0] - b[0]); 11 // query按val排序 12 Arrays.sort(queriesWithIndex, (a, b) -> a[0] - b[0]); 13 // 最小堆,按interval的宽度排序 14 PriorityQueue<int[]> minHeap = new PriorityQueue<>((a, b) -> ((a[1] - a[0]) - (b[1] - b[0]))); 15 int[] res = new int[n]; 16 int j = 0; 17 for (int i = 0; i < n; i++) { 18 int queryVal = queriesWithIndex[i][0]; 19 int queryIndex = queriesWithIndex[i][1]; 20 while (j < intervals.length && intervals[j][0] <= queryVal) { 21 minHeap.offer(intervals[j]); 22 j++; 23 } 24 while (!minHeap.isEmpty() && minHeap.peek()[1] < queryVal) { 25 minHeap.poll(); 26 } 27 res[queryIndex] = minHeap.isEmpty() ? -1 : (minHeap.peek()[1] - minHeap.peek()[0] + 1); 28 } 29 return res; 30 } 31 }
- LeetCode Interval Include Minimum Queryinterval minimum include query leetcode interval include minimum 题解minimum query 308g substrings leetcode removing minimum leetcode minimum split 2578 leetcode minimum repair 2594 leetcode minimum arrive speed leetcode minimum penalty 2483 leetcode falling minimum path operations leetcode minimum halve