1851. Minimum Interval to Include Each Query

At a Glance

Topic: intervals
Pattern: Sort + sweep + Min-heap (offline queries)
Difficulty: Hard
Companies: Google, Amazon, Meta, Microsoft, Uber
Frequency: Medium
LeetCode: 1851

Given array intervals where each element is [left, right] with size right - left + 1, and integer queries, return an array where each entry is the minimum interval size among intervals containing that query, or -1 if none.

Recognition Cues

Many queries / static intervals — offline processing (sort queries)
“Smallest length interval covering point” — among candidates with left <= query, need right >= query and minimize size
Heap sweeps stale intervals whose right endpoint fell behind current query

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

Loading diagram…

Approaches

Per query linear scan — O(queries * intervals) — too slow.
Sort intervals by left, sort queries, push intervals into min-heap keyed by (size, right) — pop top while right < query — O((n + q) log n) — optimal for typical heaps.

Optimal Solution

Go

import (
	"container/heap"
	"sort"
)

type intervalSizeEnd struct {
	size int
	end  int
}

type minHeapInterval []intervalSizeEnd

func (heapInterval minHeapInterval) Len() int { return len(heapInterval) }
func (heapInterval minHeapInterval) Less(leftIndex, rightIndex int) bool {
	left := heapInterval[leftIndex]
	right := heapInterval[rightIndex]
	if left.size != right.size {
		return left.size < right.size
	}
	return left.end < right.end
}
func (heapInterval minHeapInterval) Swap(leftIndex, rightIndex int) {
	heapInterval[leftIndex], heapInterval[rightIndex] = heapInterval[rightIndex], heapInterval[leftIndex]
}
func (heapPointer *minHeapInterval) Push(value any) {
	*heapPointer = append(*heapPointer, value.(intervalSizeEnd))
}
func (heapPointer *minHeapInterval) Pop() any {
	old := *heapPointer
	lastIndex := len(old) - 1
	item := old[lastIndex]
	*heapPointer = old[:lastIndex]
	return item
}

func minInterval(intervals [][]int, queries []int) []int {
	sort.Slice(intervals, func(leftIndex, rightIndex int) bool {
		return intervals[leftIndex][0] < intervals[rightIndex][0]
	})
	type queryWithIndex struct {
		value int
		index int
	}
	wrapped := make([]queryWithIndex, len(queries))
	for index := range queries {
		wrapped[index] = queryWithIndex{queries[index], index}
	}
	sort.Slice(wrapped, func(leftIndex, rightIndex int) bool {
		return wrapped[leftIndex].value < wrapped[rightIndex].value
	})
	answer := make([]int, len(queries))
	for index := range answer {
		answer[index] = -1
	}
	activeHeap := &minHeapInterval{}
	heap.Init(activeHeap)
	intervalPointer := 0
	for _, queryItem := range wrapped {
		queryValue := queryItem.value
		for intervalPointer < len(intervals) && intervals[intervalPointer][0] <= queryValue {
			left := intervals[intervalPointer][0]
			right := intervals[intervalPointer][1]
			size := right - left + 1
			heap.Push(activeHeap, intervalSizeEnd{size: size, end: right})
			intervalPointer++
		}
		for activeHeap.Len() > 0 && (*activeHeap)[0].end < queryValue {
			heap.Pop(activeHeap)
		}
		if activeHeap.Len() > 0 {
			answer[queryItem.index] = (*activeHeap)[0].size
		}
	}
	return answer
}

JavaScript

class MinHeap {
  constructor(compare) {
    this.data = [];
    this.compare = compare;
  }
  push(item) {
    this.data.push(item);
    this.#bubbleUp(this.data.length - 1);
  }
  pop() {
    if (this.data.length === 0) {
      return undefined;
    }
    const top = this.data[0];
    const last = this.data.pop();
    if (this.data.length > 0) {
      this.data[0] = last;
      this.#bubbleDown(0);
    }
    return top;
  }
  peek() {
    return this.data[0];
  }
  get length() {
    return this.data.length;
  }
  #parent(index) {
    return Math.floor((index - 1) / 2);
  }
  #bubbleUp(index) {
    while (index > 0) {
      const parentIndex = this.#parent(index);
      if (this.compare(this.data[index], this.data[parentIndex]) >= 0) {
        break;
      }
      [this.data[index], this.data[parentIndex]] = [
        this.data[parentIndex],
        this.data[index],
      ];
      index = parentIndex;
    }
  }
  #bubbleDown(index) {
    const length = this.data.length;
    while (true) {
      const left = index * 2 + 1;
      const right = index * 2 + 2;
      let smallest = index;
      if (left < length && this.compare(this.data[left], this.data[smallest]) < 0) {
        smallest = left;
      }
      if (right < length && this.compare(this.data[right], this.data[smallest]) < 0) {
        smallest = right;
      }
      if (smallest === index) {
        break;
      }
      [this.data[index], this.data[smallest]] = [this.data[smallest], this.data[index]];
      index = smallest;
    }
  }
}

function minInterval(intervals, queries) {
  intervals.sort((left, right) => left[0] - right[0]);
  const wrapped = queries.map((value, index) => ({ value, index }));
  wrapped.sort((left, right) => left.value - right.value);
  const answer = new Array(queries.length).fill(-1);
  const heap = new MinHeap((left, right) => {
    if (left.size !== right.size) {
      return left.size - right.size;
    }
    return left.end - right.end;
  });
  let intervalPointer = 0;
  for (const queryItem of wrapped) {
    const queryValue = queryItem.value;
    while (intervalPointer < intervals.length && intervals[intervalPointer][0] <= queryValue) {
      const left = intervals[intervalPointer][0];
      const right = intervals[intervalPointer][1];
      const size = right - left + 1;
      heap.push({ size, end: right });
      intervalPointer += 1;
    }
    while (heap.length > 0 && heap.peek().end < queryValue) {
      heap.pop();
    }
    if (heap.length > 0) {
      answer[queryItem.index] = heap.peek().size;
    }
  }
  return answer;
}

Walkthrough

Sort intervals by left. Walk queries ascending; push every interval that starts before current query. Pop heap root while its end is still left of query — it cannot cover this or any later query. Root has smallest size among survivors.

Invariant: After cleanup, every heap entry has end >= queryValue; root has minimum size among them.

Edge Cases

No interval covers query — -1
Duplicate queries — process via indexed pairs
Query equals interval endpoint — inclusive containment

Pitfalls

Heap ordered only by end — then min size is not at root
Forgetting size = right - left + 1 (inclusive length)

Variants

Count intervals per query — Fenwick / offline BIT
Dynamic insert/delete intervals — balanced tree + heap coordination
Weighted size — heap keys adjust

Mind-Map Tags

#offline-queries #interval-sweep #min-heap #sort-by-start #stale-pop