Minimum Interval to Include Each Query — Step-by-Step Visualization

Algorithm Pattern

Offline Query Processing + Min-Heap

Key Idea

Sort queries and process them in order. For each query, add all intervals that start ≤ query to a min-heap keyed by size. Pop intervals whose right end < query (expired). The heap top is the answer.

Step-by-Step Approach

1. Sort intervals by start. Sort queries (keep original index for output order).
2. For each query q (in sorted order):
3. Push all intervals with start ≤ q onto min-heap (key = size = r - l + 1).
4. Pop all intervals with end < q (they no longer cover q).
5. Heap top size is the answer for q (or -1 if empty).
6. Map answers back to original query order.

Common Gotchas

• Sort queries offline — process them in order, not the original query order.
• Heap contains (size, right) so we can check expiry without storing left.