1851. Minimum Interval to Include Each Query LeetCode Solution
In this guide, you will get 1851. Minimum Interval to Include Each Query LeetCode Solution with the best time and space complexity. The solution to Minimum Interval to Include Each Query problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of 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.
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.
Time Complexity: O(\texttt{sort}(n) + \texttt{sort}(q) + q\log n)
Space Complexity: O(n + q)
1851. Minimum Interval to Include Each Query LeetCode Solution in C++
struct T {
int size;
int right;
};
class Solution {
public:
vector<int> minInterval(vector<vector<int>>& intervals,
vector<int>& queries) {
vector<int> ans(queries.size(), -1);
auto compare = [](const T& a, const T& b) { return a.size > b.size; };
priority_queue<T, vector<T>, decltype(compare)> minHeap(compare);
vector<vector<int>> qs;
for (int i = 0; i < queries.size(); ++i)
qs.push_back({queries[i], i});
ranges::sort(intervals);
ranges::sort(qs);
int i = 0; // intervals' index
for (const vector<int>& q : qs) {
while (i < intervals.size() && intervals[i][0] <= q[0]) {
minHeap.emplace(intervals[i][1] - intervals[i][0] + 1, intervals[i][1]);
++i;
}
while (!minHeap.empty() && minHeap.top().right < q[0])
minHeap.pop();
if (!minHeap.empty())
ans[q[1]] = minHeap.top().size;
}
return ans;
}
}; /* code provided by PROGIEZ */
1851. Minimum Interval to Include Each Query LeetCode Solution in Java
class Solution {
public int[] minInterval(int[][] intervals, int[] queries) {
record T(int size, int right) {}
int[] ans = new int[queries.length];
Arrays.fill(ans, -1);
Queue<T> minHeap = new PriorityQueue<T>((a, b) -> Integer.compare(a.size, b.size));
Integer[] indices = new Integer[queries.length];
for (int i = 0; i < queries.length; ++i)
indices[i] = i;
Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
Arrays.sort(indices, (a, b) -> Integer.compare(queries[a], queries[b]));
int i = 0; // intervals' index
for (final int index : indices) {
while (i < intervals.length && intervals[i][0] <= queries[index]) {
minHeap.offer(new T(intervals[i][1] - intervals[i][0] + 1, intervals[i][1]));
++i;
}
while (!minHeap.isEmpty() && minHeap.peek().right < queries[index])
minHeap.poll();
if (!minHeap.isEmpty())
ans[index] = minHeap.peek().size;
}
return ans;
}
} // code provided by PROGIEZ
1851. Minimum Interval to Include Each Query LeetCode Solution in Python
