Minimum Interval to Include Each Query
hardTime: O((n+q) log n)Space: O(n+q)
Signals to notice
smallest interval containing each querysort and sweepheap for active intervals
Brute force first
For each query check all intervals — O(nm).
The key insight
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).
What must stay true
Sweep ensures each interval added/removed once. Min-heap by interval size gives smallest valid interval.
Easy way to go wrong
Not removing expired intervals — those ending before the query are invalid.