Minimum Interval to Include Each Query
Given a list of intervals and a list of queries, find the minimum interval that includes each query. The intervals are given as a list of pairs, where each pair represents the start and end of an interval. The queries are given as a list of integers, where each integer represents a query. The minimum interval that includes each query is the interval with the smallest length that includes all queries.
Constraints:
- 1 <= intervals.length <= 1000
- 1 <= queries.length <= 1000
- 0 <= queries[i] <= 10^9
Examples:
Input: [[1, 4], [2, 5], [6, 8]], [1, 3, 6]
Output: [1, 6]
Explanation: The minimum interval that includes all queries is [1, 6], which has a length of 5.
Solutions
Binary Search
The solution uses binary search to find the minimum interval that includes each query. It first sorts the intervals and queries, then for each query, it uses binary search to find the interval that includes the query. The minimum interval is then updated based on the length of the interval.
def min_interval(intervals, queries):
intervals.sort(key=lambda x:
x[0])
queries.sort()
result = []
for query in queries:
left, right = 0, len(intervals) - 1
while left <= right:
mid = (left + right) // 2
if intervals[mid][0] <= query and query <= intervals[mid][1]:
result.append([intervals[mid][0], intervals[mid][1]])
break
elif intervals[mid][0] > query:
right = mid - 1
else:
left = mid + 1
min_len = float('inf')
min_interval = None
for interval in result:
length = interval[1] - interval[0]
if length < min_len:
min_len = length
min_interval = interval
return min_intervalFollow-up:
What if the intervals are not sorted?
