原文链接: https://leetcode-cn.com/problems/minimum-interval-to-include-each-query
英文原文
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 <= 1051 <= queries.length <= 105intervals[i].length == 21 <= lefti <= righti <= 1071 <= queries[j] <= 107
中文题目
给你一个二维整数数组 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 <= 1051 <= queries.length <= 105queries[i].length == 21 <= lefti <= righti <= 1071 <= queries[j] <= 107
通过代码
高赞题解
包含每个查询的最小区间
预处理排序
对于查询，需要离线处理。
首先将查询列表从小向大排序，同时需要记录查询列表原本的位置信息。
将区间列表按照左端点从小到大排序，右端点从小到大排序。
遍历查询，计算结果
对于每一个查询：
首先将左端点符合条件的区间（即左端点小于或等于当前查询的值）插入到优先队列，优先队列按照区间长度，从小到大排序。
然后检查优先队列的堆顶，如果堆顶的区间的右端点满足条件（即右端点大于或者等于当前查询的值），即查询到结果。
如果不满足就弹出堆顶，继续查询下一个堆顶。
直到堆顶满足条件或者优先队列为空为止。
整理并返回结果
遍历完所有的查询之后，将查询列表按照原有的位置信息还原。
输出结果即可。
struct Query{
int val;
int index;
int len;
bool operator < (const Query& q) const{
return val < q.val;
}
};
struct Interval{
int tail;
int len;
bool operator < (const Interval& i) const{
return len > i.len;
}
};
class Solution {
public:
vector<int> minInterval(vector<vector<int>>& intervals, vector<int>& queries) {
sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b){
if(a[0] == b[0]){
return a[1] < b[1];
}else{
return a[0] < b[0];
}
});
int tail = 0;
vector<Query> qVec;
for(int i = 0; i < queries.size(); ++i){
qVec.push_back({queries[i], i, 0});
}
sort(qVec.begin(), qVec.end());
priority_queue<Interval> PQ;
for(auto& it: qVec){
while(tail < intervals.size() and intervals[tail][0] <= it.val){
PQ.push({intervals[tail][1], intervals[tail][1] - intervals[tail][0] + 1});
++tail;
}
while(!PQ.empty() and PQ.top().tail < it.val){
PQ.pop();
}
if(PQ.empty()){
it.len = -1;
}else{
it.len = PQ.top().len;
}
}
vector<int> ret(qVec.size());
for(auto& it:qVec){
ret[it.index] = it.len;
}
return ret;
}
};
统计信息
| 通过次数 | 提交次数 | AC比率 |
|---|---|---|
| 2105 | 5218 | 40.3% |
提交历史
| 提交时间 | 提交结果 | 执行时间 | 内存消耗 | 语言 |
|---|
