Skip to content

Volume ITechnology

4.27.6 — Minimum Interval to Include Each Query ​

LeetCode 1851 · Hard

The problem ​

For each query value, find the shortest interval that contains it, and return that interval's length. Return -1 if no interval contains the query.

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

For query 2, the intervals containing it are [1,4] (length 4) and [2,4] (length 3), so the answer is 3.

Restating the Problem: You are given intervals and a list of queries. For each query point, you need to find the interval that envelops that point and has the smallest total length.

  • Constraints to note: Up to 100,000 intervals and 100,000 queries. This confirms O(n^2) is impossible. We need an O(n \log n) approach.
  • Edge cases: A query might not fall into any interval, in which case we return -1. Multiple queries might ask for the same point.

The pattern ​

Checking every interval for every query is O(n \times q) — ten billion operations here. Far too slow.

Three ideas combine to fix it, and each one is worth naming separately.

Idea 1 — answer the queries out of order. Nothing says you must answer them in the order given. Sort the queries, answer them in increasing order, and put the answers back into their original positions at the end. That is called offline query processing, and it is the key that unlocks everything else: sorted queries mean you can sweep the intervals forwards and never go back.

Idea 2 — sort the intervals by start, and add them as the queries advance. When processing query q, every interval with start <= q is a candidate. Because the queries only increase, the set of candidates only grows — so each interval is added exactly once across the whole run.

Idea 3 — a min-heap keyed by length gives the shortest candidate. But some candidates have already ended before the current query, so before reading the heap's top you must discard anything with end < q.

That last step is the subtle one, and it works because the queries increase: an interval that has expired for this query has expired for every later one too, so it can be removed permanently.

The solution ​

python
import heapq

class Solution:
    def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:
        intervals.sort()                                   # (1) by start
        answer = {}  # (2)
        heap = []                                          # (3) (length, end)
        i = 0

        for q in sorted(queries):                          # (4) queries in order
            # 1. every interval that has started is a candidate
            while i < len(intervals) and intervals[i][0] <= q:  # (5)
                start, end = intervals[i]
                heapq.heappush(heap, (end - start + 1, end))  # (6)
                i += 1

            # 2. discard candidates that have already finished
            while heap and heap[0][1] < q:  # (7)
                heapq.heappop(heap)

            # 3. the top is the shortest interval still covering q
            answer[q] = heap[0][0] if heap else -1  # (8)

        return [answer[q] for q in queries]                # (9) restore the original order
ts
function minInterval(intervals: number[][], queries: number[]): number[] {
  intervals.sort((a, b) => a[0] - b[0]);  // (1)
  const answer = new Map<number, number>();  // (2)
  const heap = new MinHeap<[number, number]>((e) => e[0]);   // (3) [length, end]
  let i = 0;

  for (const q of [...queries].sort((a, b) => a - b)) {  // (4)
    while (i < intervals.length && intervals[i][0] <= q) {  // (5)
      const [s, e] = intervals[i++];
      heap.push([e - s + 1, e]);  // (6)
    }

    while (heap.size && heap.peek()![1] < q) heap.pop();  // (7)

    answer.set(q, heap.size ? heap.peek()![0] : -1);  // (8)
  }

  return queries.map(q => answer.get(q)!);  // (9)
}

Line by line ​

(1) Sort the intervals by start.

(2) The answers, keyed by query value, so they can be put back in the original order at the end.

(3) A min-heap of (length, end) for intervals that have started. The shortest one sits at the front.

(4) Answer the queries in increasing order. This is the trick that makes the problem fast. As the query value only grows, each interval only needs to be added once and removed once. Answering questions in an order you choose, rather than the order asked, is called offline processing.

(5) Every interval that starts at or before q could cover it.

(6) Add it to the heap with its length, end − start + 1. Both ends count, so the interval [2, 4] has length 3.

(7) Remove intervals that end before q. They cannot cover this query, and because later queries are even bigger, they never will. Only the front of the heap needs checking: an expired interval further back does no harm until it reaches the front.

(8) The front of the heap is the shortest interval covering q, or −1 if none does.

(9) Put the answers back in the order the queries were asked.

Four details.

The heap is keyed by length, with the end stored alongside. You want the shortest, so length is the priority; the end is needed for the expiry check.

while heap[0][1] < q uses a while, not an if. Several intervals may have expired since the last query.

Expired intervals are removed permanently, and that is what keeps the total work linear in the number of intervals. Each interval is pushed once and popped at most once — the same amortized argument as the monotonic stack in 4.8.

Code Walkthrough:

  • Sorting Inputs: We first sort the intervals by their start times.
  • Offline Queries: We process the queries in ascending sorted order, so we can sweep through the intervals left to right without backtracking.
  • Tracking Candidates (while intervals[i][0] <= q): For the current query q, we push all intervals that start at or before q into a Min-Heap. The heap prioritizes intervals by their length (end - start + 1).
  • Pruning Expired (while heap[0][1] < q): Before picking an answer, we must discard intervals from the top of the heap if they have already ended before q. We permanently pop them.
  • Recording Answers: The valid interval at the top of the heap is the shortest one covering q. We store this in a hash map answer.
  • Restoring Order: We build the final output by mapping the original queries array through our answer hash map.

A dictionary maps each query value to its answer, then the final list comprehension restores the original order. This also handles duplicate queries for free, since the same value maps to the same answer.

Trace ​

intervals = [[1,4],[2,4],[3,6],[4,4]], sorted queries [2,3,4,5].

qintervals addedexpired removedheap topanswer
2[1,4] len 4, [2,4] len 3none(3, 4)3
3[3,6] len 4none(3, 4)3
4[4,4] len 1none(1, 4)1
5none(1,4), (3,4), (4,4) all end < 5(4, 6)4

[3,3,1,4] ✓.

Query 5 is the interesting one — three candidates expire at once, which is why the removal loop is a while.

Edge cases ​

  • A query no interval covers. The heap is empty after line (7), so −1.
  • The same query asked twice. The map gives both the same answer.
  • An interval of length 1, like [3, 3]. It covers only the query 3.

Complexity ​

O((n + q) \log n) — sorting both lists, then each interval pushed and popped at most once with each heap operation O(\log n).

O(n + q) space.

  • Time Complexity: O(n \log n + q \log q). Sorting the intervals takes O(n \log n) and sorting queries takes O(q \log q). Inside the loop, every interval is pushed to the heap exactly once and popped at most once, contributing O(n \log n). Total time is O(n \log n + q \log q).
  • Space Complexity: O(n + q) to store the heap, the hash map for answers, and the sorted arrays.

Offline processing, as a technique ​

When queries can be answered in any order, sorting them is often what makes a problem tractable.

The catch is that you must have all the queries up front. It does not work if they arrive one at a time and each must be answered immediately. This distinction has a name: offline versus online.

Other problems built on it:

  • Range queries with union-find — process edges and queries together in weight order.
  • Counting smaller elements after self — merge sort or a Fenwick tree, answering as you go.
  • Kth smallest in a range — sort queries by right endpoint and sweep.

If a problem looks impossible online, ask whether it becomes easy offline. That question is the whole technique.

The alternative structures ​

If the queries had to be answered online, you would need a different structure — a segment tree or an interval tree over the coordinate range, giving O(\log n) per query with O(n \log n) preprocessing. 4.13.4 builds segment trees.

More code, and unnecessary here because the queries are all given in advance. Naming it as the online answer is a good way to close.

What the interviewer will push on ​

"Why can you reorder the queries?" Each answer is independent, so only the output order matters, and a dictionary restores it.

"Why does the heap need the end as well as the length?" To detect intervals that have expired.

"Why is the expiry removal permanent?" Queries only increase, so an expired interval never becomes relevant again.

"Why is this O((n+q)\log n) and not worse?" Each interval is pushed once and popped once across the whole run.

"What if the queries were online?" A segment tree or interval tree.

"What about duplicate queries?" The dictionary handles them with no extra work.

One thing to volunteer: name offline processing as the technique and say what it costs — all queries must be known in advance. Recognising a problem as offline-solvable is a genuinely senior observation and it is what makes this Hard problem approachable.

Next: 4.28 covers the problems where the trick is arithmetic or index manipulation rather than a data structure.

Combine chapters into one PDF

Pick the chapters you want. They print in the order you pick them.

Volume I — Technology
Part 0 — Retention & Notation
Part 1 — Foundations of Computation
Part 2 — Operating Systems
2.1 The Kernel
2.2 Processes
2.3 Threads & Scheduling
2.4 Concurrency Under the Hood
2.5 Memory Management
2.6 File Systems
2.7 Input/Output
2.8 Linux for Engineers
2.9 Windows & macOS in Practice
Part 3 — Languages, Compilers & Runtimes
3.6 JavaScript & V8
3.7 TypeScript
3.8 Node.js Internals
3.13 Python & CPython
3.14 FastAPI & Production Python
Part 4 — Data Structures & Algorithms
4.0 Classic Problems — Before NeetCode
4.4 Arrays & Hashing — Problems
4.5 Two Pointers
4.6 Sliding Window
4.8 Stack — Problems
4.9 Linked List — Problems
4.11 Binary Search — Problems
4.13 Trees
4.14 Tree — Problems
4.15 Trie — Problems
4.17 Heap — Problems
4.18 Backtracking — Problems
4.19 Graphs
4.20 Graph — Problems
4.21 Advanced Graph — Problems
4.23 1-D DP — Problems
4.24 2-D DP — Problems
4.26 Greedy — Problems
4.27 Interval — Problems
4.28 Math & Geometry — Problems
4.30 Bit Manipulation — Problems
Part 5 — Networking & the Web
5.3 IP
5.4 Transport
5.6 HTTP
Part 6 — Frontend Engineering
6.1 Browser Internals
6.2 HTML & CSS Mastery
6.3 JavaScript in the Browser
6.4 React, from First Component to Full Shop
6.5 Frameworks & Rendering
6.8 UI Engineering & Patterns
Part 7 — Databases & Storage
7.2 SQL Mastery
7.3 Storage Engine Internals
7.4 Transactions
7.5 NoSQL Taxonomy
7.8 Analytics & Big Data
Part 8 — Security, Identity & Cryptography
8.2 Cryptography
8.3 Protocols of Trust
8.4 Identity: AuthN & AuthZ
8.5 Application Security
8.6 Infrastructure Security
Part 9 — Software Design (LLD)
9.2 OOP Foundations
9.3 Design Principles
9.4 Design Patterns
9.5 Concurrency
9.6 API Design
9.7 LLD Interview Machines
9.9 Node/Express Production Playbook
Part 10 — Distributed Systems & HLD
10.7 Consistency & Consensus
10.8 Messaging & Microservices
10.14 Caching
Building blocks from the design seat
Part 11 — System Design Case Studies
Part 12 — AI & ML Engineering
12.1 What AI Engineering Is
12.2 The Math You Need
12.3 Classical Machine Learning
12.4 Data for ML
12.5 Deep Learning
12.6 Embeddings & Vector Search
12.7 Transformers & LLMs
12.8 Building with LLMs
12.9 Retrieval-Augmented Generation
12.10 Agents
12.11 Adapting Models
12.12 Production AI
12.13 Multimodal AI
12.14 AI Security & Governance
12.15 Case Studies & Capstone
Part 13 — Cloud, DevOps & Infrastructure
13.11 Git, from First Commit to Team Workflow
Part 14 — Containers: Docker & Kubernetes
14.1 Foundations
14.2 Docker
14.3 Kubernetes
14.4 Kubernetes on Azure
Part 15 — The Craft & Career
Nothing picked yet