Description
1851. Minimum Interval to Include Each Query (Hard)
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
Solution
First, it should be noted that sorting the intervals array will not affect the result. Secondly, sorting the queries array will not have a significant impact on the answer. It merely changes the order of the answers. We just need to associate the result of each query with its corresponding index in the original queries array.
For convenience, let's convert the queries array into a vector<pair<int, int>> qrs; where the first element represents the value to be queried, and the second element represents its index in the queries array. Then, we sort the qrs vector in ascending order based on the first element.
Next, we prepare to iterate through the qrs vector. Since the intervals array is already sorted in ascending order based on the left endpoint, we compare the current query with intervals[idx][0]. If intervals[idx][0] <= query, we enqueue the intervals (fulfilling half of the required conditions), and increment idx to indicate that we have considered this interval. We continue this process until idx >= queries.size() or intervals[idx][0] > query.
Next, we compare the current query with the right endpoint of the top interval in the heap (where the top interval has the smallest length). If the right endpoint is smaller than query, we pop the interval out of the heap until the heap is empty or the right endpoint of the top interval is >= query.
Finally, we can update the minimum interval length corresponding to the query.
Code
class Solution {
public:
vector<int> minInterval(vector<vector<int>> &intervals, vector<int> &queries) {
sort(intervals.begin(), intervals.end());
using pii = pair<int, int>;
vector<pii> qrs;
int m = intervals.size(), n = queries.size();
for (int i = 0; i < n; ++i) {
qrs.emplace_back(queries[i], i);
}
std::sort(qrs.begin(), qrs.end());
vector<int> ans(n, -1);
priority_queue<pii, vector<pii>, greater<pii>> pq; // pair.first => right - left + 1，pair.second => right
int idx = 0;
for (int i = 0; i < n; ++i) {
while (idx < m && intervals[idx][0] <= qrs[i].first) {
pq.push({intervals[idx][1] - intervals[idx][0] + 1, intervals[idx][1]});
++idx;
}
while (!pq.empty() && pq.top().second < qrs[i].first) {
pq.pop();
}
if (!pq.empty()) {
ans[qrs[i].second] = pq.top().first;
}
}
return ans;
}
};