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 ith
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 jth
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; } }

Todo

# 1851. Minimum Interval to Include Each Query # https://leetcode.com/problems/minimumintervaltoincludeeachquery/ class Solution: def minInterval(self, A, queries): A = sorted(A)[::1] h = [] res = {} for q in sorted(queries): while A and A[1][0] <= q: i, j = A.pop() if j >= q: heapq.heappush(h, [j  i + 1, j]) while h and h[0][1] < q: heapq.heappop(h) res[q] = h[0][0] if h else 1 return [res[q] for q in queries]