{x}
blog image

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 <= 105
  • 1 <= queries.length <= 105
  • intervals[i].length == 2
  • 1 <= lefti <= righti <= 107
  • 1 <= queries[j] <= 107

Solution Explanation: Minimum Interval to Include Each Query

This problem asks to find the size of the smallest interval containing each query. A naive approach would be to iterate through all intervals for each query, which leads to O(n*m) time complexity, where 'n' is the number of intervals and 'm' is the number of queries. This is inefficient for large inputs.

The optimal solution uses a combination of sorting, offline processing, and a priority queue (min-heap). The key idea is to process queries offline, meaning we don't need to answer each query immediately. We can sort the queries and intervals to optimize the search.

Algorithm:

  1. Sort: Sort the intervals array in ascending order based on the left endpoint (intervals[i][0]). Sort the queries array, but associate each query value with its original index to reconstruct the final answer later. We'll use tuples or pairs for this.

  2. Offline Processing: Iterate through the sorted queries. For each query q, we need to find the smallest interval containing it.

  3. Priority Queue: We maintain a priority queue (pq) containing only the relevant intervals. An interval is relevant if its left endpoint is less than or equal to the current query q.

  4. Adding Intervals: As we iterate through sorted queries, we add intervals to the pq if their left endpoint is less than or equal to the current query. The priority queue orders intervals based on their size (length).

  5. Removing Irrelevant Intervals: Before finding the smallest interval for the current query, remove intervals from the pq whose right endpoint is less than the query value. These intervals cannot contain the current query.

  6. Finding the Smallest Interval: If the pq is not empty after removing irrelevant intervals, the top element of the pq (smallest interval) contains the query. We record its size in the result array. Otherwise, no interval contains the query, so we record -1.

  7. Reconstructing the Answer: After processing all queries, we have an array with results indexed according to the original order of queries. We return this array.

Time Complexity: O(n log n + m log m + (n+m) log n), where n is the number of intervals and m is the number of queries. Sorting intervals and queries takes O(n log n) and O(m log m) respectively. Adding and removing elements from the priority queue takes O((n+m) log n) in the worst case.

Space Complexity: O(n) to store the priority queue.

Code Examples:

The code examples below implement the algorithm in different languages. The core logic remains the same across all implementations. Note the use of a min-heap priority queue (implemented differently across languages).

Python3

import heapq
 
class Solution:
    def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:
        n, m = len(intervals), len(queries)
        intervals.sort()  # Sort intervals by left endpoint
        queries_with_indices = sorted([(q, i) for i, q in enumerate(queries)]) # Sort queries with original indices
 
        result = [-1] * m
        pq = []  # Priority queue (min-heap) to store relevant intervals
        interval_index = 0
 
        for query, original_index in queries_with_indices:
            # Add relevant intervals to the priority queue
            while interval_index < n and intervals[interval_index][0] <= query:
                left, right = intervals[interval_index]
                heapq.heappush(pq, (right - left + 1, right)) # (size, right_endpoint)
                interval_index += 1
 
            # Remove irrelevant intervals from the priority queue
            while pq and pq[0][1] < query:
                heapq.heappop(pq)
 
            # Get the smallest interval containing the query, if any
            if pq:
                result[original_index] = pq[0][0]
 
        return result

Java

import java.util.*;
 
class Solution {
    public int[] minInterval(int[][] intervals, int[] queries) {
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]); // Sort intervals
 
        int[][] queriesWithIndices = new int[queries.length][2];
        for (int i = 0; i < queries.length; i++) {
            queriesWithIndices[i][0] = queries[i];
            queriesWithIndices[i][1] = i;
        }
        Arrays.sort(queriesWithIndices, (a, b) -> a[0] - b[0]); // Sort queries
 
        int[] result = new int[queries.length];
        Arrays.fill(result, -1); // Initialize with -1 (no interval found)
 
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]); // Min-heap
        int intervalIndex = 0;
 
        for (int[] queryWithIndex : queriesWithIndices) {
            int query = queryWithIndex[0];
            int originalIndex = queryWithIndex[1];
 
            // Add relevant intervals to the priority queue
            while (intervalIndex < intervals.length && intervals[intervalIndex][0] <= query) {
                int[] interval = intervals[intervalIndex];
                pq.offer(new int[]{interval[1] - interval[0] + 1, interval[1]}); // (size, right_endpoint)
                intervalIndex++;
            }
 
            // Remove irrelevant intervals
            while (!pq.isEmpty() && pq.peek()[1] < query) {
                pq.poll();
            }
 
            // Get the smallest interval
            if (!pq.isEmpty()) {
                result[originalIndex] = pq.peek()[0];
            }
        }
 
        return result;
    }
}

C++

#include <vector>
#include <algorithm>
#include <queue>
 
using namespace std;
 
class Solution {
public:
    vector<int> minInterval(vector<vector<int>>& intervals, vector<int>& queries) {
        sort(intervals.begin(), intervals.end()); // Sort intervals
 
        vector<pair<int, int>> queriesWithIndices; // (query, original_index)
        for (int i = 0; i < queries.size(); ++i) {
            queriesWithIndices.emplace_back(queries[i], i);
        }
        sort(queriesWithIndices.begin(), queriesWithIndices.end()); // Sort queries
 
 
        vector<int> result(queries.size(), -1);
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; // Min-heap
 
        int intervalIndex = 0;
 
        for (auto& queryWithIndex : queriesWithIndices) {
            int query = queryWithIndex.first;
            int originalIndex = queryWithIndex.second;
 
            // Add relevant intervals
            while (intervalIndex < intervals.size() && intervals[intervalIndex][0] <= query) {
                pq.emplace(intervals[intervalIndex][1] - intervals[intervalIndex][0] + 1, intervals[intervalIndex][1]); // (size, right_endpoint)
                intervalIndex++;
            }
 
            // Remove irrelevant intervals
            while (!pq.empty() && pq.top().second < query) {
                pq.pop();
            }
 
            // Get smallest interval
            if (!pq.empty()) {
                result[originalIndex] = pq.top().first;
            }
        }
 
        return result;
    }
};

Go

import (
	"sort"
	"container/heap"
)
 
type pair struct{ v, r int }
type hp []pair
 
func (h hp) Len() int           { return len(h) }
func (h hp) Less(i, j int) bool { return h[i].v < h[j].v }
func (h hp) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *hp) Push(v any)        { *h = append(*h, v.(pair)) }
func (h *hp) Pop() any          { a := *h; v := a[len(a)-1]; *h = a[:len(a)-1]; return v }
 
func minInterval(intervals [][]int, queries []int) []int {
	sort.Slice(intervals, func(i, j int) bool { return intervals[i][0] < intervals[j][0] })
	
	n := len(queries)
	qs := make([][2]int, n)
	ans := make([]int, n)
	for i := range queries {
		qs[i] = [2]int{queries[i], i}
		ans[i] = -1
	}
	sort.Slice(qs, func(i, j int) bool { return qs[i][0] < qs[j][0] })
	pq := &hp{}
	heap.Init(pq)
	i := 0
	for _, q := range qs {
		x, j := q[0], q[1]
		for i < len(intervals) && intervals[i][0] <= x {
			a, b := intervals[i][0], intervals[i][1]
			heap.Push(pq, pair{b - a + 1, b})
			i++
		}
		for pq.Len() > 0 && (*pq)[0].r < x {
			heap.Pop(pq)
		}
		if pq.Len() > 0 {
			ans[j] = (*pq)[0].v
		}
	}
	return ans
}

This detailed explanation and the provided code examples should help you understand the solution to this problem thoroughly. Remember to choose the code example that best suits your preferred programming language.