1851. Minimum Interval to Include Each Query

Problem Description

In this problem, we are given two primary inputs:

1. A 2D integer array named intervals. Each subarray contains two integer values [left_i, right_i] which represent an interval that starts at left_i and ends at right_i (inclusive). The size of an interval is the number of integers within that range, which is calculated using the formula right_i - left_i + 1.

2. An integer array called queries. Each value queries[j] within this array denotes a question asking for the size of the smallest interval i such that left_i <= queries[j] <= right_i. If no interval satisfies this condition for a given query, the answer is -1.

The task is to go through each query and determine the answer by finding the appropriate interval that contains the query value and has the smallest size. The result should be returned as an array of answers corresponding to the original order of the queries.

Intuition

The intuition behind the solution approach is to efficiently match queries to their smallest enclosing intervals (if they exist). We need a way to handle these possible overlaps and find the smallest intervals quickly as the number of queries can be quite large. The approach can be broken down into a few key ideas:

1. Sort the intervals by their starting point to iterate over them in order.

2. Sort the queries by their value but keep track of their original indices so we can store the answer in the right place later.

3. Use a priority queue (pq) to maintain a set of active intervals at any given query value. This priority queue will store pairs of (interval size, right endpoint) sorted by size.

4. For each query value x, add all the intervals that start at or before x to the priority queue. This ensures that at any iteration, the priority queue contains all intervals that could possibly contain x.

5. Remove from the priority queue any intervals that end before x, as these intervals can no longer contain the query value.

6. Look at the smallest interval remaining in the priority queue (which is at the front of the queue due to the sorting by size) to answer the current query. If the priority queue is empty, this means there are no valid intervals for the query, and we should record -1.

7. Repeat the process for all queries. Since the queries and intervals are sorted, we can do this in a single pass using two pointers, where one iterates over the sorted intervals and the other iterates over the sorted queries.

By using a sorted structure and a priority queue, we can efficiently manage the set of potential intervals for each query, enabling us to quickly find the smallest interval when it exists.

Learn more about Binary Search, Sorting, Line Sweep and Heap (Priority Queue) patterns.

Solution Approach

The solution to the problem leverages both sorting and a heap (priority queue) to efficiently determine the smallest interval containing each query. The implementation proceeds as follows:

1. Sort Intervals and Queries: The first step is to sort the intervals based on their starting points, so they can be processed in ascending order. Simultaneously, the queries are sorted based on their value, but each query is transformed into a tuple containing its value and original index. This transformation allows us to return the results according to the original order of queries.

2. Initialize Data Structures: A priority queue in Python is implemented using a heap, specifically through the built-in heapq module. The pq list will serve as our priority queue for the intervals. A list ans of size m (number of queries) is also initialized to -1 and will be used to store the final answer to each query.

3. Iterate Over Queries: We iterate over each sorted query value x along with the corresponding original index j. The goal during this iteration is to add any new intervals that could potentially contain x and to remove intervals that no longer apply.

4. Add Matching Intervals to Priority Queue:

   • Using a pointer i to traverse the sorted intervals, we check whether the current interval starts at or before the query value x.
   • If it does, we calculate the size of the interval by b - a + 1 (where a and b are the starting and ending points of the interval) and push a tuple (size, b) onto the priority queue (heap).
   • This ensures that the smallest intervals (by size) will be at the top of the heap.
   • Increment i to move to the next interval for future queries.

5. Remove Invalid Intervals from Priority Queue:

   • Before checking the smallest interval, we first clear out any intervals from the priority queue whose end point is before the query value x because such intervals cannot possibly contain x.
   • This is done by popping elements off the heap as long as the smallest interval's end point is less than x.

6. Retrieve the Smallest Valid Interval:

   • After potentially removing intervals, if the priority queue is not empty, the interval at the top of the heap is the smallest interval that contains x.
   • We set ans[j] (where j is the original index of the query) to the size of this interval.

7. Return Results: Finally, after all queries have been processed, we return the array ans, which contains the size of the smallest interval corresponding to each query in the order they were originally presented.

By sorting the intervals and queries and using a min-heap to keep track of active intervals, this approach efficiently manages the various size intervals that could satisfy the range condition for each query, allowing us to determine the minimum interval size required in an optimized manner.

Example Walkthrough

Let's illustrate the solution approach using a small example.

Suppose our input intervals array is [[1,4], [2,5], [6,8]], and the queries array is [3, 5, 7].

1. Sort Intervals and Queries:

   • Firstly, we sort the intervals by their start point, which doesn’t change the order in this case: [[1,4], [2,5], [6,8]].
   • Then, sort the queries [3, 5, 7]. They are already sorted, so we transform them into pairs of values and original indices: [(3, 0), (5, 1), (7, 2)].

2. Initialize Data Structures:

   • We create a priority queue pq, which starts as an empty list [].
   • An ans list is initialized to store the results: [-1, -1, -1] (since there are 3 queries).

3. Iterate Over Queries:

   • Begin by processing the query value 3 and its corresponding index 0.

4. Add Matching Intervals to Priority Queue:

   • We check intervals starting with [1,4]. Since 1 <= 3, we calculate its size 4 - 1 + 1 = 4 and add (4, 4) to the priority queue.
   • Next, the interval [2,5]. Since 2 <= 3, its size is 5 - 2 + 1 = 4, and we add (4, 5) to the priority queue.
   • The queue now has [(4, 4), (4, 5)].

5. Remove Invalid Intervals from Priority Queue:

   • No intervals end before 3, so nothing is removed.

6. Retrieve the Smallest Valid Interval:

   • The top of the heap is (4, 4), so ans at the original index 0 is updated to 4.

Next, we process the remaining queries. For 5, both [1,4] and [2,5] are considered, but [1,4] is removed since it doesn't contain 5. The heap has [(4, 5)], and the answer to query 5 is 4.

For 7, [6,8] is considered and (3, 8) is added to the heap. After removing intervals that end before 7, we get the smallest interval size 3 for query 7.

7. Return Results:
   • The final results array is [4, 4, 3]: the smallest intervals containing each query value respectively.

By following these steps, we effectively matched each query to its smallest enclosing interval, if such one existed, and obtained the solution to our problem.

Python Solution

1from heapq import heappush, heappop
2from typing import List
3
4class Solution:
5    def min_interval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:
6        # Sort intervals by starting points
7        intervals.sort()
8        # Pair each query with its original index and sort by the query value
9        sorted_queries = sorted((query, index) for index, query in enumerate(queries))
10      
11        # Initialize the result list with -1, assuming interval is not found
12        result = [-1] * len(queries)
13        # A priority queue to store intervals as we process the queries
14        priority_queue = []
15      
16        # 'interval_index' tracks the index of the current interval being processed
17        interval_index = 0
18      
19        # Loop through each query in sorted_queries
20        for query_value, query_index in sorted_queries:
21            # Add to the priority_queue all intervals that start before or at the query value
22            while interval_index < len(intervals) and intervals[interval_index][0] <= query_value:
23                start, end = intervals[interval_index]
24                interval_size = end - start + 1
25                # Add the interval size and the end value to the priority_queue
26                heappush(priority_queue, (interval_size, end))
27                interval_index += 1
28          
29            # Remove intervals from the priority_queue that end before the query value
30            while priority_queue and priority_queue[0][1] < query_value:
31                heappop(priority_queue)
32          
33            # If there is an interval that includes the query value, record its size
34            if priority_queue:
35                result[query_index] = priority_queue[0][0]
36      
37        return result
38
39# Example usage:
40# sol = Solution()
41# print(sol.min_interval([[1,4],[2,4],[3,6]], [2,3,4,5])) # Output: [3,3,3,4]
42

Java Solution

1class Solution {
2    public int[] minInterval(int[][] intervals, int[] queries) {
3        int numIntervals = intervals.length, numQueries = queries.length;
4      
5        // Sort the intervals based on their starting points
6        Arrays.sort(intervals, (interval1, interval2) -> interval1[0] - interval2[0]);
7      
8        // Pair each query with its original index and sort by query value
9        int[][] queriesWithIndices = new int[numQueries][];
10        for (int i = 0; i < numQueries; ++i) {
11            queriesWithIndices[i] = new int[] { queries[i], i };
12        }
13        Arrays.sort(queriesWithIndices, (query1, query2) -> query1[0] - query2[0]);
14      
15        // Initialize the answer array with -1 (indicating no interval found)
16        int[] answer = new int[numQueries];
17        Arrays.fill(answer, -1);
18      
19        // Use a priority queue to store intervals with smallest size (end - start + 1) on top
20        PriorityQueue<int[]> minHeap = new PriorityQueue<>((interval1, interval2) -> interval1[0] - interval2[0]);
21        int index = 0;
22      
23        // Process each query
24        for (int[] queryWithIndex : queriesWithIndices) {
25            int queryValue = queryWithIndex[0];
26          
27            // Add intervals to the priority queue where the start is less than or equal to the query value
28            while (index < numIntervals && intervals[index][0] <= queryValue) {
29                int start = intervals[index][0], end = intervals[index][1];
30                minHeap.offer(new int[] { end - start + 1, end });
31                ++index;
32            }
33          
34            // Remove intervals from the queue which end before the query value
35            while (!minHeap.isEmpty() && minHeap.peek()[1] < queryValue) {
36                minHeap.poll();
37            }
38          
39            // If the queue is not empty, there is an interval covering the query value
40            if (!minHeap.isEmpty()) {
41                // The size of the smallest interval covering the query is stored in the answer array
42                answer[queryWithIndex[1]] = minHeap.peek()[0];
43            }
44        }
45      
46        return answer; // Return the array containing the size of smallest interval covering each query
47    }
48}
49

C++ Solution

1class Solution {
2public:
3    vector<int> minInterval(vector<vector<int>>& intervals, vector<int>& queries) {
4        // n is the number of intervals, m is the number of queries
5        int n = intervals.size(), m = queries.size();
6      
7        // Sort the intervals based on start times
8        sort(intervals.begin(), intervals.end());
9      
10        using Pair = pair<int, int>; // Defining Pair as a shorthand
11
12        // Create a vector to store queries and their original indices
13        vector<Pair> sortedQueries;
14        for (int i = 0; i < m; ++i) {
15            sortedQueries.emplace_back(queries[i], i);
16        }
17
18        // Sort the queries based on their values
19        sort(sortedQueries.begin(), sortedQueries.end());
20      
21        // Answer array with default values -1 (no interval found case)
22        vector<int> ans(m, -1);
23
24        // Min-heap to store the smallest interval covering x and its end time
25        priority_queue<Pair, vector<Pair>, greater<Pair>> minHeap;
26
27        // Index to track the next interval to examine
28        int index = 0;
29
30        // Iterate over sorted queries
31        for (auto& [queryValue, originalIndex] : sortedQueries) {
32            // Add all intervals that start before or at the current query value
33            while (index < n && intervals[index][0] <= queryValue) {
34                int start = intervals[index][0], end = intervals[index][1];
35                // Push the interval size and end value into the heap
36                minHeap.emplace(end - start + 1, end);
37                ++index;
38            }
39
40            // Remove intervals from heap that don't cover the current query value
41            while (!minHeap.empty() && minHeap.top().second < queryValue) {
42                minHeap.pop();
43            }
44
45            // If the heap is not empty, the top element is the smallest interval covering x
46            if (!minHeap.empty()) {
47                ans[originalIndex] = minHeap.top().first;
48            }
49        }
50
51        // Return the filled answer array
52        return ans;
53    }
54};
55

Typescript Solution

1type Interval = [number, number];
2type Query = number;
3type QueryWithIndex = [number, number];
4type HeapElement = [number, number];
5
6// Function that sorts an array of intervals
7function sortIntervals(intervals: Interval[]): Interval[] {
8    return intervals.sort((a, b) => a[0] - b[0]);
9}
10
11// Function that sorts queries and maintains original indices
12function sortQueries(queries: Query[]): QueryWithIndex[] {
13    return queries.map((query, index) => [query, index])
14                  .sort((a, b) => a[0] - b[0]);
15}
16
17// Function to execute the main logic of finding minimum intervals for queries
18function minInterval(intervals: Interval[], queries: Query[]): number[] {
19    const n: number = intervals.length;
20    const m: number = queries.length;
21    let sortedIntervals: Interval[] = sortIntervals(intervals);
22    let sortedQueries: QueryWithIndex[] = sortQueries(queries);
23    let answerArray: number[] = new Array(m).fill(-1);  // Initialize answer array with -1 (no interval case)
24  
25    // Min-heap to store the smallest interval covering x and its end time
26    let minHeap: HeapElement[] = [];
27
28    // Helper function to push elements to the heap
29    const pushHeap = (size: number, endValue: number) => {
30        minHeap.push([size, endValue]);
31        minHeap.sort((a, b) => a[0] - b[0]);
32    };
33
34    // Helper function to pop the top element from the heap
35    const popHeap = () => {
36        minHeap.shift();
37    };
38
39    // Index to track the next interval to examine
40    let index = 0;
41
42    // Iterate over sorted queries
43    for (const [queryValue, originalIndex] of sortedQueries) {
44        // Add all intervals starting at or before the current query value
45        while (index < n && sortedIntervals[index][0] <= queryValue) {
46            const start = sortedIntervals[index][0];
47            const end = sortedIntervals[index][1];
48            // Push the interval size and end value into the heap
49            pushHeap(end - start + 1, end);
50            index++;
51        }
52
53        // Remove intervals that don't cover the current query
54        while (minHeap.length > 0 && minHeap[0][1] < queryValue) {
55            popHeap();
56        }
57
58        // If the heap is not empty, set the answer as the size of the smallest covering interval
59        if (minHeap.length > 0) {
60            answerArray[originalIndex] = minHeap[0][0];
61        }
62    }
63
64    // Return the filled answer array
65    return answerArray;
66}
67

Time and Space Complexity

Time Complexity:

The time complexity of the code can be broken down into the following parts:

1. Sorting the intervals: n is the number of intervals, and this step takes O(n log n) time using the Timsort algorithm (Python's built-in sorting algorithm).

2. Sorting the queries along with their original indices: m is the number of queries, and this step also takes O(m log m) time.

3. Traversing the sorted queries and intervals: Each interval and query is checked at most once, which is O(m + n).

4. Heap operations: In the worst case, every interval can be pushed and popped once. Given that the priority queue (min-heap) can contain at most n elements, each push and pop operation takes O(log n). Therefore, if all n intervals are pushed and popped, it would take O(n log n).

Summing up the complexities, we have O(n log n) + O(m log m) for the sorting operations and O(m + n) for the linear traversal, and O(n log n) for heap operations. The most significant terms are the ones that involve sorting and heap operations, thus overall time complexity is O(n log n + m log m).

Space Complexity:

For space complexity:

1. The intervals and the extra space for storing the sorted queries and their original indices require O(n) and O(m) space respectively.

2. The priority queue (min-heap) can contain up to n elements at any time, and therefore, requires O(n) space.

Therefore, the space complexity is O(n + m) when considering the intervals, queries, and the min-heap storage.

Learn more about how to find time and space complexity quickly.