Minimum Interval to Include Each Query 🧠
LeetCode Link: Minimum Interval to Include Each Query
Difficulty: Hard
Problem Explanation 📝
Problem: LeetCode 1851 - Minimum Interval to Include Each Query
Description: You are given a 2D integer array intervals, where intervals[i] = [lefti, righti] describes the ith interval starting from lefti and ending at righti (inclusive). The size of the array is n and 1-indexed.
You are also given an integer array queries, where queries[j] = [leftj, rightj] describes the jth query starting from leftj and ending at rightj (inclusive). The size of the array is m and 1-indexed.
Find the minimum interval for each query such that it is completely covered by an interval in intervals and lci <= leftj <= rightj <= rci.
Return an integer array answer, where answer[j] is the minimum interval length for the jth query.
Intuition: To solve this problem efficiently, we can use a two-step approach:
- Sort both intervals and queries in ascending order based on their lengths.
- Use a priority queue (min heap) to keep track of the right boundaries of the current intervals.
Approach:
- Create two separate vectors of pairs: one for intervals and one for queries, where the first element of each pair represents the length of the interval/query, and the second element is the index of the interval/query in the original arrays.
- Sort both vectors in ascending order based on their lengths.
- Initialize a priority queue (min heap) to keep track of the right boundaries of the current intervals. We'll insert the intervals in the queue based on their right boundary.
- Iterate through the sorted intervals: a. While the current query length is smaller or equal to the current interval length, update the result for the query and remove it from the priority queue.
- Continue to process the next interval.
- Return the answer vector containing the minimum interval lengths for each query.
⌛ Time Complexity: The time complexity is O(n log n + m log m), where n is the number of intervals and m is the number of queries. Sorting both vectors of pairs takes O(n log n + m log m) time, and processing intervals and queries takes O(n + m log n) time.
💾 Space Complexity: The space complexity is O(n + m) to store the vectors of pairs and the priority queue.
Solutions 💡
Cpp 💻
class Solution {
public:
vector<int> minInterval(vector<vector<int>> &intervals, vector<int> &queries) {
vector<int> sortedQueries = queries;
// [size of interval, end of interval]
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
// {query -> size of interval}
unordered_map<int, int> m;
// Also need only valid intervals, so sort by start time & sort queries
sort(intervals.begin(), intervals.end());
sort(sortedQueries.begin(), sortedQueries.end());
vector<int> result;
int i = 0;
for (int j = 0; j < sortedQueries.size(); j++) {
int query = sortedQueries[j];
// Push intervals into the min heap whose start time is less than or equal to the current query value
while (i < intervals.size() && intervals[i][0] <= query) {
int left = intervals[i][0];
int right = intervals[i][1];
pq.push({right - left + 1, right});
i++;
}
// Pop the invalid intervals from the min heap (intervals whose end time is less than the current query value)
while (!pq.empty() && pq.top().second < query) {
pq.pop();
}
// Store the minimum interval size for the current query in the unordered_map
if (!pq.empty()) {
m[query] = pq.top().first;
} else {
m[query] = -1;
}
}
// Build the result vector using the unordered_map for each query
for (int j = 0; j < queries.size(); j++) {
result.push_back(m[queries[j]]);
}
return result;
}
};
Python 🐍
import heapq
class Solution:
def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:
intervals.sort(key=lambda x: x[0])
queries_sorted = sorted(enumerate(queries), key=lambda x: x[1])
min_heap = []
ans = [-1] * len(queries)
i = 0
for query_index, query in queries_sorted:
while i < len(intervals) and intervals[i][0] <= query:
start, end = intervals[i]
heapq.heappush(min_heap, (end - start + 1, end))
i += 1
while min_heap and min_heap[0][1] < query:
heapq.heappop(min_heap)
if min_heap:
ans[query_index] = min_heap[0][0]
return ans