1003. Smallest Covering Interval
A museum publishes intervals[i] = [a, b], the opening hours (in minutes) of exhibit i; if a > b the two numbers are swapped, and both ends are inclusive, so the exhibit is open for b - a + 1 minutes in total. Each entry of queries is a minute of the day.
For every query minute return the length (b - a + 1) of the shortest exhibit window containing that minute, or -1 when no window contains it. Return the answers in the order of queries.
Checking every window for every query is too slow. Aim for O((n + q) log n) time and O(n + q) space.
Example 1
- Input:
- intervals = [[12,19],[4,9],[7,15],[22,26],[16,16]]queries = [8,16,3,24,20]
- Output:
- [6,1,-1,5,-1]
- Explanation:
Query 8 lies in [4,9] (length 6) and [7,15] (length 9), so 6; query 16 lies in [12,19] (length 8) and [16,16] (length 1), so 1; 3 and 20 are covered by nothing; 24 lies only in [22,26], length 5.
Example 2
- Input:
- intervals = [[30,10],[25,25],[18,40]]queries = [10,26,25,41]
- Output:
- [21,21,1,-1]
- Explanation:
The first interval is read as [10,30] (length 21). Queries 10 and 26 are covered only by it; 25 is covered by [25,25] of length 1; 41 is outside every interval.
Constraints
1 ≤ n = intervals.length ≤ 105
0 ≤ q = queries.length ≤ 2000
1 ≤ a, b, queries[j] ≤ 200000
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,600 msC++ 400 msJava 800 msJavaScript 800 msTypeScript 800 ms
Expected complexity
- Time
- O((n + q) log n)
- Space
- O(n + q)