LeetCode #1851 Hard

Minimum Interval to Include Each Query

For every value in queries, return the length of the smallest interval containing it, or -1.

intervalsheapsortingoffline-query

02

Intuition

Scanning all intervals for every query repeats the same containment tests and costs O(nq). Sort the queries so interval eligibility changes in one direction: as the query grows, add every interval whose left endpoint has been reached. Among those candidates, order intervals by length in a min-heap and lazily remove any whose right endpoint lies before the current query. What remains contains the query, and the shortest remaining interval is at the heap top.

How to spot this pattern

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.

03

Approach

1

Sort queries without losing their original positions

Pair each query with its index and process those pairs by query value. Offline sorting lets one interval pointer move forward exactly once. Store each answer at the saved index so duplicate queries and the original order are handled naturally.

2

Add intervals when their left endpoint becomes eligible

Sort intervals by left endpoint. For a query q, push every interval with left <= q into a min-heap keyed by (length, right). Intervals starting later cannot contain q, while all earlier-starting intervals are now candidates until they expire.

3

Discard expired intervals and read the shortest survivor

Pop heap entries while their right < q; those intervals can never answer this or any later sorted query. If the heap is non-empty, its top has the smallest length among intervals that start before and end after q; otherwise store -1. Each interval enters and leaves the heap at most once.

04

Solution

▶1class Solution:
▶2    def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:
▶3        intervals.sort(key=lambda interval: interval[0])
▶4        ordered_queries = sorted((query, i) for i, query in enumerate(queries))
▶5        answer = [-1] * len(queries)
▶6        heap = []
▶7        index = 0
▶8 
▶9        for query, original_index in ordered_queries:
▶10            while index < len(intervals) and intervals[index][0] <= query:
▶11                left, right = intervals[index]
▶12                length = right - left + 1
▶13                heapq.heappush(heap, (length, right))
▶14                index += 1
▶15 
▶16            while heap and heap[0][1] < query:
▶17                heapq.heappop(heap)
▶18 
▶19            if heap:
▶20                answer[original_index] = heap[0][0]
▶21 
▶22        return answer

05

Common pitfalls

Adding intervals too late

✗ Wrong

while index < len(intervals) and intervals[index][0] < query:

✓ Right

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

✗ Wrong

while heap and heap[0][1] <= query:

✓ Right

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

✗ Wrong

answer.append(heap[0][0])

✓ Right

answer[original_index] = heap[0][0]

Queries are reordered for processing, so results must be written back using their saved original indices.

06

Edge cases

A query is equal to an interval endpoint

Both endpoints are inclusive, so left <= query <= right keeps that interval eligible.

No interval contains a query

After adding eligible starts and removing expired ends, the heap is empty and the answer is -1.

The same query value appears multiple times

Each (query, original_index) pair receives the same heap-derived length at its own output position.

07

Complexity

Time

O(n log n + q log q + (n + q) log n)

Space

O(n + q)

Every interval is pushed once and popped at most once.