LeetCode 1851: Minimum Interval To Include Each Query — Step-by-Step Visual Trace

#python #leetcode #algorithms

Medium — Heap | Sorting | Array | Greedy

The Problem

Given a list of intervals and queries, find the minimum length interval that contains each query point, returning -1 if no interval contains the query.

Approach

Sort intervals by start time and queries by value. Use a min-heap to track valid intervals by length, adding intervals as queries progress and removing expired ones. The heap maintains the smallest valid interval for each query.

Time: O(n log n + m log m + (n + m) log n) · Space: O(n + m)

Code

import heapq

class Solution:
    def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:
        intervals.sort(key=lambda x: x[0])
        queries_sorted = sorted(enumerate(queries), key=lambda x: x[1])

        min_heap = []
        ans = [-1] * len(queries)
        i = 0

        for query_index, query in queries_sorted:
            while i < len(intervals) and intervals[i][0] <= query:
                start, end = intervals[i]
                heapq.heappush(min_heap, (end - start + 1, end))
                i += 1

            while min_heap and min_heap[0][1] < query:
                heapq.heappop(min_heap)

            if min_heap:
                ans[query_index] = min_heap[0][0]

        return ans