Approach Summary
Sort intervals and queries. Sweep queries in order; add intervals whose start ≤ query to a min-heap by size. Remove stale entries (end < query).
How to Recognize This Pattern
- Offline query + sweep line + min-heap
- Process queries in sorted order, lazy-evict heap
Complexity Analysis
Time Complexity
O((n + q) log n)
Space Complexity
O(n + q)
Tags
Array Binary Search Line Sweep Sorting Heap