Formatted question description: https://leetcode.ca/all/1851.html

# 1851. Minimum Interval to Include Each Query

## Level

Medium

## Description

You are given a 2D integer array `intervals`

, where `intervals[i] = [left_i, right_i]`

describes the `i-th`

interval starting at `left_i`

and ending at `right_i`

**(inclusive)**. The **size** of an interval is defined as the number of integers it contains, or more formally `right_i - left_i + 1`

.

You are also given an integer array `queries`

. The answer to the `j-th`

query is the size of the smallest interval `i`

such that `left_i <= queries[j] <= right_i`

. 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 <= 10^5`

`1 <= queries.length <= 10^5`

`intervals[i].length == 2`

`1 <= left_i <= right_i <= 10^7`

`1 <= queries[j] <= 10^7`

## Solution

Use a tree map to store the query results, and use a tree set to store the queries that do not have results yet. Initially, put all the elements in `queries`

into the tree set. Sort `intervals`

according to the intervals’ sizes.

Loop over `intervals`

. For each interval, obtain the start and the end of the interval and calculate the size of the interval. For all the elements in the tree set that are in the range `[start, end]`

, these queries’ results are the size of the current interval, so put the query results into the tree map and remove these queries from the tree set.

Finally, create an array to store the queries’ results and return the array.

```
class Solution {
public int[] minInterval(int[][] intervals, int[] queries) {
TreeMap<Integer, Integer> map = new TreeMap<Integer, Integer>();
TreeSet<Integer> set = new TreeSet<Integer>();
for (int query : queries)
set.add(query);
int intervalsCount = intervals.length;
Arrays.sort(intervals, new Comparator<int[]>() {
public int compare(int[] interval1, int[] interval2) {
int length1 = interval1[1] - interval1[0] + 1, length2 = interval2[1] - interval2[0] + 1;
if (length1 != length2)
return length1 - length2;
else
return interval1[0] - interval2[0];
}
});
for (int i = 0; i < intervalsCount; i++) {
int[] interval = intervals[i];
int start = interval[0], end = interval[1];
int size = end - start + 1;
Set<Integer> subSet = new HashSet<Integer>(set.subSet(start, true, end, true));
for (int num : subSet) {
map.put(num, size);
set.remove(num);
}
}
int queriesCount = queries.length;
int[] answers = new int[queriesCount];
for (int i = 0; i < queriesCount; i++)
answers[i] = map.getOrDefault(queries[i], -1);
return answers;
}
}
```