How do you solve Minimum Interval to Include Each Query?

Sort intervals by start. Sort queries. Iterate queries in ascending order, pushing intervals starting before or at the query onto a min-heap keyed by interval size and end. Pop intervals from the heap that end before the query. If the heap is not empty, the top element corresponds to the smallest interval containing the query. Store this result in a map keyed by query. Finally, return results in the original query order.

Minimum Interval to Include Each Query

Q: What is the time complexity of Minimum Interval to Include Each Query?

O((n + m) log n). Sorting intervals and queries takes O(n log n) and O(m log m) respectively. Each interval is pushed and popped at most once from the heap, each operation O(log n). Each query is processed once, resulting in O(m log n) for heap operations. Overall complexity is O((n + m) log n).

Q: What pattern does Minimum Interval to Include Each Query use?

The Pattern: Heap / Priority Queue (Dynamic Candidate Filtering) The Heuristic: When needing to find the minimal or maximal element among dynamically changing candidates constrained by a moving parameter (like a query), use a heap to efficiently add candidates as they become relevant and remove those that become invalid, ensuring the top of the heap always reflects the current optimal choice.

Medium Heap / Priority Queue

Problem

Given a list of intervals and a list of queries, return an array where each element is the size of the smallest interval that contains the corresponding query, or -1 if no such interval exists.

1 ≤ intervals.length ≤ 10⁵
1 ≤ queries.length ≤ 10⁵
intervals[i].length == 2
1 ≤ intervals[i][0] ≤ intervals[i][1] ≤ 10⁷
1 ≤ queries[i] ≤ 10⁷

Example

Input: intervals = [[1,4],[2,4],[3,6],[4,4]], queries = [2,3,4,5]

Output: [3,3,1,4]

Sort intervals by start: [[1,4],[2,4],[3,6],[4,4]]. For query 2, intervals [1,4] and [2,4] contain it; smallest size is 4-1+1=4 and 4-2+1=3, so 3 is chosen. For query 3, intervals [1,4],[2,4],[3,6] contain it; smallest size is 3 again. For query 4, intervals [1,4],[2,4],[3,6],[4,4] contain it; smallest size is 1 (from [4,4]). For query 5, only [3,6] contains it with size 4.

Approach

Straightforward Solution

A naive approach checks each query against all intervals to find the minimal containing interval, resulting in O(n*m) time complexity (n = intervals, m = queries), which is infeasible for large inputs.

Core Observation

The smallest interval containing a query is the interval with the minimal length that covers the query point. Intervals can overlap, so multiple intervals may contain the same query. Efficiently finding the minimal such interval for each query requires a data structure that can dynamically track candidate intervals as queries progress.

Path to Optimal

Preview

Sorting intervals by their start points and queries in ascending order allows processing intervals and queries in a coordinated manner. Using a min-heap keyed by interval size enables efficient retrieval of the smallest interval currently covering the query…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Sort intervals by start. Sort queries…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O((n + m) log n)

Sorting intervals and queries takes O(n log n) and O(m log m) respectively. Each interval is pushed and popped at most once from the heap, each operation O(log n). Each query is processed once, resulting in O(m log n) for heap operations. Overall complexity is O((n + m) log n).

Space

O(n)

The min-heap stores intervals that are candidates for queries. In the worst case, all intervals may be in the heap simultaneously, requiring O(n) auxiliary space.

Pattern Spotlight

Heap / Priority Queue (Dynamic Candidate Filtering)

When needing to find the minimal or maximal element among dynamically changing candidates constrained by a moving parameter (like a query), use a heap to efficiently add candidates as they become relevant and remove those that become invalid, ensuring the top of the heap always reflects the current optimal choice.

Solution

Python

1import heapq
2
3class Solution:
  def minInterval(self, intervals: list[list[int]], queries: list[int]) -> list[int]:
      intervals.sort()
      
      min_heap = []
      res = {}
      i = 0
      
      for q in sorted(queries):
          while i < len(intervals) and intervals[i][0] <= q:
              l, r = intervals[i]
              heapq.heappush(min_heap, (r - l + 1, r))
              i += 1
          
          while min_heap and min_heap[0][1] < q:
              heapq.heappop(min_heap)
          
          if min_heap:
              res[q] = min_heap[0][0]
          else:
              res[q] = -1
      
      return [res[q] for q in queries]

Step-by-Step Solution

Sort Intervals to Enable Sequential Processing by Start Point

5	`intervals.sort()`

Objective

To arrange intervals in ascending order by their start points to facilitate efficient incremental processing alongside sorted queries.

Key Insight

Sorting intervals by start allows the algorithm to process intervals in a single pass, pushing only those intervals that could possibly contain the current query. This ordering is essential to avoid repeatedly scanning all intervals for each query, reducing complexity from O(n*m) to O(n log n + m log n).

Interview Quick-Check

Core Logic

Sorting intervals by start ensures that when processing queries in ascending order, intervals can be added to the heap exactly once when their start is less than or equal to the query.

Common Pitfalls & Bugs

Failing to sort intervals leads to repeated scanning or incorrect heap contents, causing inefficiency or incorrect results.

Iterate Queries in Sorted Order, Adding Relevant Intervals to Min-Heap

To process queries in ascending order, pushing intervals that start before or at the query onto a min-heap keyed by interval size and end point.

Remove Intervals from Heap That Do Not Cover Current Query

To discard intervals from the heap whose end points are less than the current query, ensuring only intervals containing the query remain.

Record the Smallest Interval Size or -1 for Each Query

To store the size of the smallest interval containing the query if any exist, or -1 if none do.

Return Results in Original Query Order

To produce the final output array by mapping each original query to its computed minimal interval size or -1.

4 more steps with full analysis available on Pro.

Line Analysis

This solution has 4 Critical lines interviewers watch for.

Line 12 Critical

while i < len(intervals) and intervals[i][0] <= q:

While intervals start before or at the query, add them to the heap.

This loop adds all intervals that could potentially cover the current query, ensuring the heap contains all relevant candidates.

Line 14 Critical

heapq.heappush(min_heap, (r - l + 1, r))

Push the interval onto the min-heap keyed by size and end point.

Heap ordering by interval size ensures the smallest interval containing the query is always accessible at the top.

Line 17 Critical

while min_heap and min_heap[0][1] < q:

Remove intervals from the heap that end before the query.

Discarding intervals that cannot contain the query maintains heap correctness and ensures the top interval is valid.

Full line-by-line criticality + rationale for all 16 lines available on Pro.

Test Your Understanding

Why does the algorithm remove intervals from the heap that end before the current query?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Minimum Interval to Include Each Query from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Minimum Interval to Include Each Query drill

or drill a free problem

1	`import heapq`
2
3	`class Solution:`
4	`def minInterval(self, intervals: list[list[int]], queries: list[int]) -> list[int]:`
5	`intervals.sort()`
6
7	`min_heap = []`
8	`res = {}`
9	`i = 0`
10
11	`for q in sorted(queries):`
12	`while i < len(intervals) and intervals[i][0] <= q:`
13	`l, r = intervals[i]`
14	`heapq.heappush(min_heap, (r - l + 1, r))`
15	`i += 1`
16
17	`while min_heap and min_heap[0][1] < q:`
18	`heapq.heappop(min_heap)`
19
20	`if min_heap:`
21	`res[q] = min_heap[0][0]`
22	`else:`
23	`res[q] = -1`
24
25	`return [res[q] for q in queries]`