Minimum Interval to Include Each Query
Hard · Trees · Array · Binary Search · Line Sweep · Sorting · Heap (Priority Queue)
Problem
You are given a list of closed intervals intervals[i] = [left_i, right_i]. The size of an interval is right_i - left_i + 1, the number of integers it contains. You are also given an array queries.
For each queries[j], find the smallest-size interval i with left_i <= queries[j] <= right_i and report its size, or -1 if no interval contains the query. Return the answers as an array in the same order as queries.
Examples
Input: intervals = [[1,6],[3,4],[8,8]], queries = [3,5,8,7] Output: [2,6,1,-1]
3 is inside [3,4] (size 2); 5 only fits [1,6] (size 6); 8 fits [8,8] (size 1); 7 fits nothing.
Input: intervals = [[2,9]], queries = [1,9] Output: [-1,8]
1 is left of the interval; 9 is its right end, and ends count.
Input: intervals = [[1,10],[2,9],[4,5]], queries = [4,2,10] Output: [2,8,10]
4 is in all three, the smallest is [4,5] (size 2); 2 is in [2,9] (size 8); 10 only in [1,10].
Constraints
- 1 <= len(intervals) <= 10^5
- 1 <= len(queries) <= 10^5
- len(intervals[i]) == 2
- 1 <= left_i <= right_i <= 10^7
- 1 <= queries[j] <= 10^7
Approaches
- Check every interval for every query — time O(n · q), space O(1) beyond the answer
Follow-up
If queries had to be answered online, one at a time in the given order, you could compress coordinates and build a segment tree that stores, for each point, the smallest size of an interval covering it (range "chmin" updates, point queries). That is O((n + q) log(n + q)) as well, without reordering queries.
Related problems
Start free on Cariara · Coding problems · System design studio
