Minimum Interval to Include Each Query

Minimum Interval to Include Each Query

1. What is this problem about?

The "Minimum Interval to Include Each Query" is a challenging "Hard" difficulty problem involving ranges and queries. You are given a set of intervals [start, end] and a set of queries (points). For each query, you need to find the size of the smallest interval that contains that point. The size of an interval [start, end] is calculated as end - start + 1. If no interval contains the point, return -1.

This problem is about efficient searching. Since there can be many intervals and many queries, a naive $O(N \times Q)$ approach where you check every interval for every query will be far too slow.

2. Why is this asked in interviews?

Companies like Google and Bloomberg ask this to test advanced data structure knowledge. It requires combining Sorting, Priority Queues, and the Offline Query technique.

Key evaluation points:

• Preprocessing: Does the candidate realize that sorting both intervals and queries is the key to efficiency?
• Data Structure Choice: Can the candidate use a Min-Heap to keep track of the "smallest" valid interval?
• Pointers/Iterators: Managing the flow of adding intervals as the query point moves forward.

3. Algorithmic pattern used

The Offline Query + Min-Heap pattern is the most effective:

1. Sort Everything: Sort intervals by their start time. Sort the queries while keeping track of their original indices.
2. Iterate through Queries: For each query (from smallest to largest):
   • Add all intervals that start at or before the query point into a Min-Heap. The heap should store [size, end_time].
   • Remove intervals from the top of the heap that end before the current query point (they are no longer valid).
   • The interval at the top of the heap is the smallest one that covers the current query point.
3. Record Results: Map the result back to the query's original position.

4. Example explanation

Intervals: [[1, 4], [2, 3], [3, 6]], Queries: [2, 5] Sorted Intervals: [[1, 4], [2, 3], [3, 6]]

1. Query 2:
   • Intervals starting $\le 2$: [1, 4] (size 4), [2, 3] (size 2).
   • Heap: [[2, 3], [4, 4]].
   • Top is [2, 3]. It ends at 3, which is $\ge 2$. Valid!
   • Result for query 2: 2.
2. Query 5:
   • Add intervals starting $\le 5$: [3, 6] (size 4).
   • Heap: [[2, 3], [4, 4], [4, 6]].
   • Remove invalid: [2, 3] ends at 3 (invalid for point 5). [1, 4] ends at 4 (invalid for point 5).
   • Top is [3, 6] (size 4). It ends at 6, which is $\ge 5$. Valid!
   • Result for query 5: 4.

5. Common mistakes candidates make

• Not Sorting Queries: Trying to process queries in their original order, which forces you to re-add and re-remove intervals repeatedly.
• Heap Management: Forgetting to remove stale intervals from the heap, leading to incorrect "smallest" values.
• Size Calculation: Using end - start instead of end - start + 1.

6. Interview preparation tip

Learn the "Offline Query" technique. When you have multiple queries and the "state" of the system changes linearly (like points moving along a timeline), sorting the queries allows you to process the entire set in one sweep.