Minimum interval to include each query

Array Binary Search Sweep Line Sorting Heap (Priority Queue)

54.0% acceptance

Feb 25, 2026

1138

You are given a 2D integer array intervals, where intervals[i] = [lefti, righti] describes the ith interval starting at lefti and ending at righti (inclusive). The size of an interval is defined as the number of integers it contains, or more formally righti - lefti + 1. You are also given an integer array queries. The answer to the jth query is the size of the smallest interval i such that lefti <= queries[j] <= righti. If no such interval exists, the answer is -1. Return an array containing the answers to the queries.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

use std::collections::BinaryHeap;
use std::cmp::Reverse;

impl Solution {
  pub fn min_interval(mut intervals: Vec<Vec<i32>>, queries: Vec<i32>) -> Vec<i32> {
    intervals.sort_unstable_by_key(|iv| iv[0]);

    let k = queries.len();
    let mut sorted_q: Vec<usize> = (0..k).collect();
    sorted_q.sort_unstable_by_key(|&i| queries[i]);

    // min-heap of (size, right)
    let mut heap: BinaryHeap<Reverse<(i32, i32)>> = BinaryHeap::new();
    let mut answer = vec![-1i32; k];
    let mut iv_idx = 0usize;

    for qi in sorted_q {
      let q = queries[qi];
      // Add all intervals with left <= q
      while iv_idx < intervals.len() && intervals[iv_idx][0] <= q {
        let l = intervals[iv_idx][0];
        let r = intervals[iv_idx][1];
        heap.push(Reverse((r - l + 1, r)));
        iv_idx += 1;
      }
      // Remove intervals with right < q
      while let Some(&Reverse((_, r))) = heap.peek() {
        if r < q {
          heap.pop();
        } else {
          break;
        }
      }
      if let Some(&Reverse((size, _))) = heap.peek() {
        answer[qi] = size;
      }
    }

    answer
  }
}