Minimum Interval to Include Each Query
HardIntervals
You are given a list of closed intervals intervals, where intervals[i] = [left, right] contains every integer from left to right inclusive. The size of an interval is the number of integers it contains: right - left + 1.
You are also given an integer array queries. For each queries[j], find the smallest size of any interval that contains it, meaning left <= queries[j] <= right. If no interval contains queries[j], the answer for it is -1.
Return an array answer with answer[j] being the answer for queries[j], in the same order as queries. Queries may repeat. Neither input is sorted.
Example 1
- Input:
- intervals = [[1, 3], [2, 8], [5, 6], [10, 10]], queries = [6, 2, 9, 10, 4]
- Output:
- [2, 3, -1, 1, 7]
- Explanation
- Query 6 is inside
[2, 8](size 7) and[5, 6](size 2), so the answer is 2. Query 2 is inside[1, 3](size 3) and[2, 8], giving 3. Nothing contains 9, so -1. Query 10 is inside[10, 10](size 1). Query 4 is only inside[2, 8], giving 7.
Example 2
- Input:
- intervals = [[5, 9], [5, 6]], queries = [5, 7, 5]
- Output:
- [2, 5, 2]
- Explanation
- Query 5 fits in both intervals and
[5, 6](size 2) is smaller. Query 7 only fits in[5, 9](size 5). Repeated queries are answered independently, in their original positions.
Example 3
- Input:
- intervals = [[3, 7], [7, 12]], queries = [7, 12, 3]
- Output:
- [5, 6, 5]
- Explanation
- Endpoints count as inside. 7 is in both intervals, and
[3, 7]has size 5 versus 6. 12 is only in[7, 12]and 3 is only in[3, 7].
Constraints
1 <= intervals.length <= 10^51 <= queries.length <= 10^5intervals[i].length == 21 <= left <= right <= 10^71 <= queries[j] <= 10^7