Problem

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.

Examples

Example 1:

1
2
3
4
5
6
7

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:

1
2
3
4
5
6
7

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.

Solution

Method 1 - Sort the intervals

To solve this problem efficiently:

  1. Sort intervals and queries:
    • Sort intervals by their start point (left) and then by their size (right - left), as smaller intervals should be preferred when resolving queries.
    • Sort queries, keeping track of their original indices, so we can return results in the original order.
  2. Use a min-heap to track active intervals:
    • Use a min-heap to maintain active intervals. The heap will store intervals sorted by size.
    • As we iterate over queries, add intervals to the heap when their start (left) is less than or equal to the current query.
    • Remove intervals from the heap if their end (right) is less than the current query.
  3. Answer each query:
    • For each query, examine the smallest interval in the heap. If it’s valid (covers the current query), use its size as the answer.
    • If no valid interval exists, return -1 for that query.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

public class Solution {
    public int[] minInterval(int[][] intervals, int[] queries) {
        // Sort intervals by start, then by size
        Arrays.sort(intervals, (a, b) -> {
            int cmp = Integer.compare(a[0], b[0]);
            return cmp == 0 ? Integer.compare((a[1] - a[0] + 1), (b[1] - b[0] + 1)) : cmp;
        });
        
        // Pair queries with their original indices and sort by query value
        int[][] indexedQueries = new int[queries.length][2];
        for (int i = 0; i < queries.length; i++) {
            indexedQueries[i] = new int[]{queries[i], i};
        }
        Arrays.sort(indexedQueries, Comparator.comparingInt(a -> a[0]));
        
        PriorityQueue<int[]> heap = new PriorityQueue<>(Comparator.comparingInt(a -> a[0])); // Min-heap
        int[] ans = new int[queries.length];
        Arrays.fill(ans, -1);
        
        int i = 0; // Pointer for intervals
        
        for (int[] query : indexedQueries) {
            int q = query[0];
            int idx = query[1];
            
            // Add intervals to the heap whose start <= current query
            while (i < intervals.length && intervals[i][0] <= q) {
                int left = intervals[i][0];
                int right = intervals[i][1];
                heap.offer(new int[]{right - left + 1, right, left});
                i++;
            }
            
            // Remove intervals from the heap whose end < current query
            while (!heap.isEmpty() && heap.peek()[1] < q) {
                heap.poll();
            }
            
            // Use the heap's smallest interval if it covers the current query
            if (!heap.isEmpty() && heap.peek()[2] <= q && q <= heap.peek()[1]) {
                ans[idx] = heap.peek()[0];
            }
        }
        
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

class Solution:
    def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:
        # Sort intervals by start, then by size
        intervals.sort(key=lambda x: (x[0], x[1] - x[0] + 1))
        
        # Sort queries, tracking original indices
        indexed_queries = sorted(enumerate(queries), key=lambda x: x[1])
        
        heap = []  # Min-heap to store intervals by size
        i = 0  # Pointer for intervals
        ans: List[int] = [-1] * len(queries)  # Result array
        
        for idx, q in indexed_queries:
            # Add intervals to the heap whose start <= current query
            while i < len(intervals) and intervals[i][0] <= q:
                left, right = intervals[i]
                heapq.heappush(heap, (right - left + 1, right, left))
                i += 1
            
            # Remove intervals from the heap whose end < current query
            while heap and heap[0][1] < q:
                heapq.heappop(heap)
            
            # Use the heap's smallest interval if it covers the current query
            if heap and heap[0][2] <= q <= heap[0][1]:
                ans[idx] = heap[0][0]
        
        return ans

Complexity

  • ⏰ Time complexity: O(n * log(n) + m * log(m))
    • Sorting intervals and queries: O(n * log(n) + m * log(m)) where n is the number of intervals and m is the number of queries.
    • Adding to/removing from the heap: Each interval is added/removed once, so it’s O(n * log(n)).
    • Query processing: Each query involves heap operations and interval additions/removals, totalling O(m * log(n)).
    • Total Time Complexity: O(n * log(n) + m * log(m)).
  • 🧺 Space complexity: O(n + m)
    • Min-heap: Stores up to n intervals, so O(n) space.
    • Sorting indices: O(m) for tracking query indices.
    • Total Space Complexity: O(n + m).