Pattern Recognition Drill
Hard Intervals
The Problem
Given intervals and queries (points), for each query find the size of the smallest interval containing it.
What approach would you use?
Think about it before scrolling down.
Sort queries and intervals. For each query, push valid intervals to min-heap. Pop expired. O((n+q) log n).
For each query, binary search for valid intervals. Less efficient without sorting.
Common Trap
Process queries offline (sorted) to avoid redundant work. Don't scan all intervals per query.