Minimum Interval to Include Each Query
Minimum Interval to Include Each Query: for every value in queries, return the length of the smallest interval containing it, or -1.
- 1 <= intervals.length <= 10⁵
- 1 <= queries.length <= 10⁵
- intervals[i].length == 2
- 1 <= lefti <= righti <= 10⁷
- 1 <= queries[j] <= 10⁷
Intuition
Minimum interval to include each query answers, for every query point, the size of the smallest interval containing it. Checking each query against every interval is O(q × n) and too slow at the given limits. The key move is to stop treating the queries in their given order: - Sort both the intervals and the queries, then sweep through the queries in increasing order, admitting intervals as they become relevant. Processing queries in sorted order means each interval only ever needs adding once. Since the queries only increase, an interval whose start exceeds the current query is irrelevant now and can wait. A min-heap keyed by interval size then answers each query. Before answering, push every interval whose start is at or before the query point, then discard from the heap's top any interval whose end is before the query — those have expired. After that cleanup, the heap's top is the smallest interval still covering the query, which is the answer. An empty heap means no interval contains the point, so the answer is −1. The two-sided condition is what makes the heap correct. Pushing checks the start; popping checks the end. Checking only one side leaves intervals in the heap that no longer cover the query, and the smallest of those is returned as a wrong answer. Because the queries are answered out of order, the results must be mapped back to the original query positions. Losing that mapping is a silent failure — the values are right but attached to the wrong queries. Each interval is pushed and popped once, giving O((n + q) log n) after the sorts.
Many point queries asking for the best covering interval can often be answered offline. Sort the points so candidate intervals enter monotonically, then use a heap to choose the best active interval and lazily remove expired ones.
Approach
Before reading on: price up what sorting first costs here, then ask what sorting by one endpoint makes obvious that was hidden before. Aim for O(n log n + q log q + (n + q) log n) time and O(n + q) space.
Sort both inputs
Sort intervals by start and queries by value. Processing queries in increasing order means each interval is added exactly once, which removes the repeated scanning.
Preserve the original query order
Record each query's original index before sorting. Answers are produced out of order, and losing the mapping attaches correct values to the wrong queries.
Admit intervals by start
Before answering a query, push every interval whose start is at or before it. Intervals starting later remain irrelevant until a larger query arrives.
Key the heap by size
A min-heap ordered by interval length puts the smallest candidate at the top, which is what each query asks for.
Discard expired intervals
Pop from the top while the interval's end is before the query. Checking only the start leaves stale intervals in the heap and returns wrong answers.
Read the top or return -1
After cleanup, the heap's top is the smallest covering interval. An empty heap means no interval contains the point, so the answer is -1.
Cost of the sweep
Sorting is O(n log n + q log q), and each interval is pushed and popped once, giving O((n + q) log n) overall with O(n) heap space.
Solution & live demo
Common pitfalls
Adding intervals too late
while index < len(intervals) and intervals[index][0] < query:
while index < len(intervals) and intervals[index][0] <= query:
An interval starting exactly at the query contains it because endpoints are inclusive.
Keeping intervals that end before the query
while heap and heap[0][1] <= query:
while heap and heap[0][1] < query:
An end equal to the query is valid; only ends strictly smaller have expired.
Returning answers in sorted-query order
answer.append(heap[0][0])
answer[original_index] = heap[0][0]
Queries are reordered for processing, so results must be written back using their saved original indices.
Edge cases
Both endpoints are inclusive, so left <= query <= right keeps that interval eligible.
After adding eligible starts and removing expired ends, the heap is empty and the answer is -1.
Each (query, original_index) pair receives the same heap-derived length at its own output position.