Intervals Merging and scheduling
511. Minimum Interval to Include Each Query
You are given a list of intervals, where intervals[i] = [left, right] covers every integer from left
to right, both ends included. The size of an interval is the number of integers it covers,
right - left + 1.
You are also given an array of integers queries. For each query q, find the smallest interval that
contains q, that is, an interval with left ≤ q ≤ right. The answer to the query is the size of that
interval, or -1 if no interval contains q.
Return the answers in the same order as queries.
Example 1
Input: intervals = [[3, 7], [5, 6], [1, 12], [9, 10]]
queries = [6, 2, 9, 13]
[2,12,2,-1]Explanation: 6 is in [3,7], [5,6] and [1,12], and the smallest of them, [5,6], has size 2. Only [1,12]
contains 2. 9 is in [1,12] and [9,10], so its answer is 2. No interval reaches 13.
Example 2
Input: intervals = [[-4, -4], [-6, 0], [2, 2]]
queries = [-4, -1, 2, 1]
[1,7,1,-1]Explanation: [-4,-4] covers only -4, so its size is 1. -1 is only in [-6,0], which covers 7 integers. 1 falls in
the gap between [-6,0] and [2,2].
Example 3
Input: intervals = [[-1000000000, 1000000000]]
queries = [0, 1000000000]
[2000000001,2000000001]Explanation: The one interval covers 2000000001 integers, and both queries are inside it. The second query is its right end.
Check your understanding
Work out the answer for this input before you write any code.
Constraints
1 ≤ intervals.length ≤ 105intervals[i].length = 2-109 ≤ left ≤ right ≤ 1091 ≤ queries.length ≤ 105-109 ≤ queries[j] ≤ 109
Clarifying questions
What you would ask an interviewer before writing any code.