# Minimum Interval to Include Each Query
**Difficulty:** HARD
[External](https://leetcode.com/problems/minimum-interval-to-include-each-query)
Canonical: https://scaleengineer.com/dsa/problems/minimum-interval-to-include-each-query
**Patterns:** [Line Sweep](https://scaleengineer.com/dsa/patterns/line-sweep)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search), [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array, Heap (Priority Queue)
---
## 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_.

**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`

# Approaches
## Brute Force
This is the most straightforward approach. For each query, we perform a linear scan through all the intervals. We check every single interval to see if it contains the query point. If it does, we calculate its size and compare it with the minimum size found so far for that specific query. We repeat this process for all queries.
**Time:** O(N * M), where N is the number of intervals and M is the number of queries. For each of the M queries, we iterate through all N intervals, leading to a quadratic time complexity. · **Space:** O(M), where M is the number of queries. This space is used to store the result array. If the output array is not considered, the space complexity is O(1).
**Pros:** Simple to understand and implement.; Requires minimal auxiliary data structures.
**Cons:** Extremely inefficient for large inputs.; Will cause a 'Time Limit Exceeded' (TLE) error on competitive programming platforms for the given constraints.
### Explanation
The brute-force method involves two nested loops. The outer loop iterates through each query in the `queries` array. For each query, the inner loop iterates through every interval in the `intervals` array. Inside the inner loop, we check if the current query value lies within the bounds of the current interval (`left <= query <= right`). If it does, we compute the interval's size (`right - left + 1`) and update a `minSize` variable if this new size is smaller. After the inner loop completes, the `minSize` variable will hold the size of the smallest interval containing the query. If no such interval was found, we assign -1. This result is stored in an answer array at the corresponding index of the query.

```java
class Solution {
    public int[] minInterval(int[][] intervals, int[] queries) {
        int[] ans = new int[queries.length];
        for (int i = 0; i < queries.length; i++) {
            int query = queries[i];
            int minSize = Integer.MAX_VALUE;
            boolean found = false;
            for (int[] interval : intervals) {
                int left = interval[0];
                int right = interval[1];
                if (query >= left && query <= right) {
                    int size = right - left + 1;
                    minSize = Math.min(minSize, size);
                    found = true;
                }
            }
            if (found) {
                ans[i] = minSize;
            } else {
                ans[i] = -1;
            }
        }
        return ans;
    }
}
```
### Algorithm
1. Initialize an `answers` array of the same size as `queries`, filled with `-1`.
2. For each query `q` at index `j` in `queries`:
3.   Initialize `minSize` to a very large number (e.g., `Integer.MAX_VALUE`).
4.   Iterate through each interval `[left, right]` in the `intervals` array.
5.   Check if the interval contains the query: `left <= q <= right`.
6.   If it does, calculate its size `s = right - left + 1`.
7.   Update `minSize = min(minSize, s)`.
8.   After checking all intervals, if `minSize` was updated, set `answers[j] = minSize`.
9. Return the `answers` array.

## Offline Processing with Sorting and Min-Heap
A significantly more efficient approach is to process the queries 'offline'. Instead of handling queries in their given order, we sort both the queries and the intervals. This allows us to use a two-pointers-like technique combined with a min-heap. As we iterate through the sorted queries, we add any newly relevant intervals to a min-heap. The min-heap efficiently keeps track of the smallest-sized interval that is currently 'active' and contains the query point.
**Time:** O(N log N + M log M). Sorting intervals takes O(N log N), and sorting queries takes O(M log M). The main loop involves iterating through M queries, and each of the N intervals is pushed and popped from the heap at most once. Heap operations take O(log N) time. The overall complexity is dominated by the sorting steps. · **Space:** O(N + M), where N is the number of intervals and M is the number of queries. O(M) is needed for storing indexed queries and the result. The min-heap can store up to N intervals in the worst case, requiring O(N) space.
**Pros:** Highly efficient, with a time complexity that can handle large constraints.; This 'offline processing' pattern is a powerful technique applicable to many similar problems.
**Cons:** More complex to implement compared to the brute-force approach.; Requires sorting, which modifies the order of queries, necessitating extra space to track original indices.
### Explanation
The core idea is to avoid re-scanning all intervals for each query. By sorting both intervals (by start point) and queries (by value), we can process them in a single pass. We also need to store the original indices of the queries to reconstruct the final answer array in the correct order.

We use a min-heap to store candidate intervals, prioritized by their size. We iterate through the sorted queries. For a given query `q`, we first add all intervals that start at or before `q` into the min-heap. These are the intervals that could potentially contain `q`. The heap stores pairs of `[size, right_endpoint]`. 

Next, we must prune the heap by removing intervals that are no longer valid for query `q`. An interval is invalid if it ends before `q` (i.e., `right_endpoint < q`). Since the heap is ordered by size, not by endpoint, we check the top element: if its `right_endpoint` is less than `q`, we pop it and repeat. After this cleanup, the top of the heap, if it exists, will be the interval with the minimum size that contains `q`. We use this size for our answer. If the heap is empty, no interval contains `q`.

```java
import java.util.Arrays;
import java.util.PriorityQueue;

class Solution {
    public int[] minInterval(int[][] intervals, int[] queries) {
        // Sort intervals by start time
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));

        // Create indexed queries to keep track of original indices
        int[][] indexedQueries = new int[queries.length][2];
        for (int i = 0; i < queries.length; i++) {
            indexedQueries[i][0] = queries[i];
            indexedQueries[i][1] = i;
        }

        // Sort queries by value
        Arrays.sort(indexedQueries, (a, b) -> Integer.compare(a[0], b[0]));

        // Min-heap to store [size, right_endpoint] of active intervals
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));
        
        int[] result = new int[queries.length];
        int intervalIdx = 0;

        for (int i = 0; i < queries.length; i++) {
            int queryVal = indexedQueries[i][0];
            int originalIdx = indexedQueries[i][1];

            // Add all intervals that start at or before the current query value
            while (intervalIdx < intervals.length && intervals[intervalIdx][0] <= queryVal) {
                int left = intervals[intervalIdx][0];
                int right = intervals[intervalIdx][1];
                int size = right - left + 1;
                pq.offer(new int[]{size, right});
                intervalIdx++;
            }

            // Remove intervals from the heap that end before the current query value
            while (!pq.isEmpty() && pq.peek()[1] < queryVal) {
                pq.poll();
            }

            // The top of the heap is the smallest valid interval
            if (!pq.isEmpty()) {
                result[originalIdx] = pq.peek()[0];
            } else {
                result[originalIdx] = -1;
            }
        }

        return result;
    }
}
```
### Algorithm
1. Create an array `indexedQueries` to store pairs of `(query_value, original_index)`.
2. Sort the `intervals` array based on the `left` endpoint.
3. Sort the `indexedQueries` array based on `query_value`.
4. Initialize a `result` array of size `M` (number of queries).
5. Initialize a min-heap (PriorityQueue) `pq` to store pairs `[size, right_endpoint]`.
6. Initialize an interval pointer `intervalIdx = 0`.
7. For each `(q, originalIdx)` in the sorted `indexedQueries`:
8.   While `intervalIdx < N` and `intervals[intervalIdx][0] <= q`:
9.     Calculate `size = intervals[intervalIdx][1] - intervals[intervalIdx][0] + 1`.
10.    Add `{size, intervals[intervalIdx][1]}` to the min-heap `pq`.
11.    Increment `intervalIdx`.
12.  While `pq` is not empty and `pq.peek()[1] < q`:
13.    Remove the top element from `pq` (as it ends before the query).
14.  If `pq` is not empty, the answer is the size from the top element: `result[originalIdx] = pq.peek()[0]`.
15.  Otherwise, no interval contains the query: `result[originalIdx] = -1`.
16. Return `result`.

# Solutions
### Java

```java
class Solution {
public
  int[] minInterval(int[][] intervals, int[] queries) {
    int n = intervals.length, m = queries.length;
    Arrays.sort(intervals, (a, b)->a[0] - b[0]);
    int[][] qs = new int[m][0];
    for (int i = 0; i < m; ++i) {
      qs[i] = new int[]{queries[i], i};
    }
    Arrays.sort(qs, (a, b)->a[0] - b[0]);
    int[] ans = new int[m];
    Arrays.fill(ans, -1);
    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b)->a[0] - b[0]);
    int i = 0;
    for (int[] q : qs) {
      while (i < n && intervals[i][0] <= q[0]) {
        int a = intervals[i][0], b = intervals[i][1];
        pq.offer(new int[]{b - a + 1, b});
        ++i;
      }
      while (!pq.isEmpty() && pq.peek()[1] < q[0]) {
        pq.poll();
      }
      if (!pq.isEmpty()) {
        ans[q[1]] = pq.peek()[0];
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<int> minInterval(vector<vector<int>> &intervals,
                          vector<int> &queries) {
    int n = intervals.size(), m = queries.size();
    sort(intervals.begin(), intervals.end());
    using pii = pair<int, int>;
    vector<pii> qs;
    for (int i = 0; i < m; ++i) {
      qs.emplace_back(queries[i], i);
    }
    sort(qs.begin(), qs.end());
    vector<int> ans(m, -1);
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    int i = 0;
    for (auto &[x, j] : qs) {
      while (i < n && intervals[i][0] <= x) {
        int a = intervals[i][0], b = intervals[i][1];
        pq.emplace(b - a + 1, b);
        ++i;
      }
      while (!pq.empty() && pq.top().second < x) {
        pq.pop();
      }
      if (!pq.empty()) {
        ans[j] = pq.top().first;
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]: n, m = len(intervals), len(queries) intervals . sort() queries = sorted((x, i) for i, x in enumerate(queries)) ans = [- 1] * m pq = [] i = 0 for x, j in queries: while i < n and intervals[i][0] <= x: a, b = intervals[i] heappush(pq, (b - a + 1, b)) i += 1 while pq and pq[0][1] < x: heappop(pq) if pq: ans[j] = pq[0][0] return ans

```