Minimum Interval to Include Each Query
HardArrayMatrixSQL
Description
Given 2D array intervals and array queries, for each query find the size of the smallest interval containing it. Return -1 if no interval contains the query.
Examples
Input:
intervals = [[1,4],[2,4],[3,6],[4,4]], queries = [2,3,4,5]Output:
[3,3,1,4]Explanation:
Each query's smallest containing interval size.
Input:
intervals = [[1]], queries = [2,3,4,5]Output:
[1]Explanation:
Single interval [1] is a point. None of queries 2,3,4,5 fall within this point interval.
Input:
intervals = [[2,5],[1,8],[3,4],[6,7]], queries = [1,3,5,9]Output:
[8,2,4,-1]Explanation:
For query 1: only interval [1,8] contains it (size = 8-1+1 = 8). For query 3: intervals [2,5], [1,8], and [3,4] contain it, smallest is [3,4] (size = 2). For query 5: intervals [2,5] and [1,8] contain it, smallest is [2,5] (size = 4). For query 9: no interval contains it, so return -1.
Constraints
- •
1 ≤ intervals.length ≤ 10⁵ - •
1 ≤ queries.length ≤ 10⁵
Ready to solve this problem?
Practice solo and sharpen your skills for technical interviews.