Minimum Interval to Include Each Query
You are given a 2D integer array intervals, where intervals[i] = [left_i, right_i] represents the ith interval starting at left_i and ending at right_i (inclusive).
You are also given an integer array of query points queries. The result of query[j] is the length of the shortest interval i such that left_i <= queries[j] <= right_i. If no such interval exists, the result of this query is -1.
Return an array output where output[j] is the result of query[j].
Note: The length of an interval is calculated as right_i - left_i + 1.
Example 1:
Input: intervals = [[1,3],[2,3],[3,7],[6,6]], queries = [2,3,1,7,6,8]
Output: [2,2,3,5,1,-1]Explanation:
- Query = 2: The interval
[2,3]is the smallest one containing 2, it's length is 2. - Query = 3: The interval
[2,3]is the smallest one containing 3, it's length is 2. - Query = 1: The interval
[1,3]is the smallest one containing 1, it's length is 3. - Query = 7: The interval
[3,7]is the smallest one containing 7, it's length is 5. - Query = 6: The interval
[6,6]is the smallest one containing 6, it's length is 1. - Query = 8: There is no interval containing 8.
Constraints:
1 <= intervals.length <= 10001 <= queries.length <= 10001 <= left_i <= right_i <= 100001 <= queries[j] <= 10000
Recommended Time & Space Complexity
You should aim for a solution as good or better than O(nlogn + mlogm) time and O(n + m) space, where m is the size of the array queries and n is the size of the array intervals.
Hint 1
A brute force approach would be to iterate through each query and, for each query, check all intervals to find the result. This would be an O(m * n) solution. Can you think of a better way? Maybe processing the queries in sorted order could help.
Hint 2
We sort the intervals by start value and process the queries in ascending order. Using a pointer i, we add intervals to a min-heap while their start values are less than or equal to the query, storing their end values and sizes.
Hint 3
The min-heap is ordered by interval size. We remove elements from the heap while the top element’s end value is less than the current query. The result for the query is the top element’s size if the heap is non-empty; otherwise, it is -1.