Minimum Interval to Include Each Query
hardTime: O((n+q) log n)Space: O(n+q)
Recognize the pattern
smallest interval containing each querysort and sweepheap for active intervals
Brute force idea
For each query check all intervals — O(nm).
Better approach
Sort intervals by start, queries by value. Sweep: add intervals starting ≤ query to min-heap (by size). Remove expired. Heap top = answer. O((n+m) log n).
Key invariant
Sweep ensures each interval added/removed once. Min-heap by interval size gives smallest valid interval.
Watch out for
Not removing expired intervals — those ending before the query are invalid.