Minimum Interval to Include Each Query

Hard · Intervals · Explanation and code example

Min Segment Tree (Lazy Propagation)

How it works

For each query q, we need the length of the smallest interval [l, r] such that l <= q <= r.
If no interval covers q, the answer is -1.

This solution treats the number line as a set of discrete important points (all interval endpoints and all queries).
Then it uses a segment tree that supports:

  • Range update: “For every point covered by this interval, the best (minimum) interval length might become smaller.”
  • Point query: “At this query point, what is the minimum interval length that covers it?”

Since many intervals update large ranges, we use lazy propagation to apply updates efficiently without touching every point in the range.

Because coordinates can be large, we first do coordinate compression:

  • map every unique coordinate to a compact index 0..M-1
  • this allows the segment tree to work on a small index range

Steps

  1. Collect all important points
    • Add every interval start and end
    • Add every query value
  2. Coordinate compress
    • Sort and deduplicate points
    • Create a map compress[value] -> index
  3. Build a min segment tree with lazy propagation
    • Each node stores the minimum interval length applied to that segment
    • Lazy values store “pending minimum updates” that still need to be pushed down
  4. Apply each interval as a range update
    • For interval [l, r]:
      • convert to compressed indices [L, R]
      • compute its length len = r - l + 1
      • update the segment tree on range [L, R] with len using:
        • tree[node] = min(tree[node], len)
      • lazy propagation ensures this is efficient
  5. Answer each query with a point query
    • Convert query q to compressed index idx
    • Query the segment tree at idx to get the minimum covering length
    • If the value is still infinity, return -1 (no interval covers it)
  6. Return answers in the original query order.

Complexity

  • Time complexity: O((n + m)log k)
  • Space complexity:
    • O(k) extra space.
    • O(m) space for the output array.

Where m is the length of the array queries, n is the length of the array intervals and k is the number of unique points.

Things to watch for

Losing Original Query Order After Sorting

When sorting queries for efficient processing, the original indices must be preserved. Returning results in sorted query order instead of the original order produces incorrect output. Always pair each query with its original index before sorting.

Forgetting to Remove Expired Intervals from the Heap

Intervals that have ended (their right endpoint is less than the current query) must be removed from the heap before answering. Failing to pop expired intervals means the heap may return an interval that does not actually contain the query point.

Incorrect Event Ordering in Sweep Line Approach

When multiple events occur at the same coordinate, processing order matters. Interval end events should typically be processed before query events at the same point to ensure intervals ending exactly at the query point are still considered active.

Using Wrong Interval Length Calculation

The length of interval [l, r] is r - l + 1, not r - l. This off-by-one error affects which interval is considered smallest and leads to incorrect results when intervals differ by exactly one unit.

Not Handling Queries Outside All Intervals

When no interval covers a query, the answer must be -1. Forgetting to initialize the result array with -1 or not checking for an empty heap after removing expired intervals causes undefined or incorrect values to be returned.

Python code example

from typing import List

class SegmentTree:
    def __init__(self, N):
        self.n = N
        self.tree = [float('inf')] * (4 * N)
        self.lazy = [float('inf')] * (4 * N)

    def propagate(self, treeidx, lo, hi):
        if self.lazy[treeidx] != float('inf'):
            self.tree[treeidx] = min(self.tree[treeidx], self.lazy[treeidx])
            if lo != hi:
                self.lazy[2 * treeidx + 1] = min(self.lazy[2 * treeidx + 1], self.lazy[treeidx])
                self.lazy[2 * treeidx + 2] = min(self.lazy[2 * treeidx + 2], self.lazy[treeidx])
            self.lazy[treeidx] = float('inf')

    def update(self, treeidx, lo, hi, left, right, val):
        self.propagate(treeidx, lo, hi)
        if lo > right or hi < left:
            return
        if lo >= left and hi <= right:
            self.lazy[treeidx] = min(self.lazy[treeidx], val)
            self.propagate(treeidx, lo, hi)
            return
        mid = (lo + hi) // 2
        self.update(2 * treeidx + 1, lo, mid, left, right, val)
        self.update(2 * treeidx + 2, mid + 1, hi, left, right, val)
        self.tree[treeidx] = min(self.tree[2 * treeidx + 1], self.tree[2 * treeidx + 2])

    def query(self, treeidx, lo, hi, idx):
        self.propagate(treeidx, lo, hi)
        if lo == hi:
            return self.tree[treeidx]
        mid = (lo + hi) // 2
        if idx <= mid:
            return self.query(2 * treeidx + 1, lo, mid, idx)
        else:
            return self.query(2 * treeidx + 2, mid + 1, hi, idx)

    def update_range(self, left, right, val):
        self.update(0, 0, self.n - 1, left, right, val)

    def query_point(self, idx):
        return self.query(0, 0, self.n - 1, idx)

class Solution:
    def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:
        points = []
        for interval in intervals:
            points.append(interval[0])
            points.append(interval[1])
        for q in queries:
            points.append(q)

        # Compress the coordinates
        points = sorted(set(points))
        compress = {points[i]: i for i in range(len(points))}

        # Lazy Segment Tree
        segTree = SegmentTree(len(points))

        for interval in intervals:
            start = compress[interval[0]]
            end = compress[interval[1]]
            length = interval[1] - interval[0] + 1
            segTree.update_range(start, end, length)

        ans = []
        for q in queries:
            idx = compress[q]

            # query for minSize
            res = segTree.query_point(idx)
            ans.append(res if res != float('inf') else -1)
        return ans

C++ code example

class SegmentTree {
public:
    int n;
    vector<int> tree;
    vector<int> lazy;

    SegmentTree(int N) {
        this->n = N;
        tree.assign(4 * N, INT_MAX);
        lazy.assign(4 * N, INT_MAX);
    }

    void propagate(int treeidx, int lo, int hi) {
        if (lazy[treeidx] != INT_MAX) {
            tree[treeidx] = min(tree[treeidx], lazy[treeidx]);
            if (lo != hi) {
                lazy[2 * treeidx + 1] = min(lazy[2 * treeidx + 1], lazy[treeidx]);
                lazy[2 * treeidx + 2] = min(lazy[2 * treeidx + 2], lazy[treeidx]);
            }
            lazy[treeidx] = INT_MAX;
        }
    }

    void update(int treeidx, int lo, int hi, int left, int right, int val) {
        propagate(treeidx, lo, hi);

        if (lo > right || hi < left) return;

        if (lo >= left && hi <= right) {
            lazy[treeidx] = min(lazy[treeidx], val);
            propagate(treeidx, lo, hi);
            return;
        }

        int mid = (lo + hi) / 2;
        update(2 * treeidx + 1, lo, mid, left, right, val);
        update(2 * treeidx + 2, mid + 1, hi, left, right, val);

        tree[treeidx] = min(tree[2 * treeidx + 1], tree[2 * treeidx + 2]);
    }

    int query(int treeidx, int lo, int hi, int idx) {
        propagate(treeidx, lo, hi);
        if (lo == hi) return tree[treeidx];

        int mid = (lo + hi) / 2;
        if (idx <= mid) return query(2 * treeidx + 1, lo, mid, idx);
        else return query(2 * treeidx + 2, mid + 1, hi, idx);
    }

    void update(int left, int right, int val) {
        update(0, 0, n - 1, left, right, val);
    }

    int query(int idx) {
        return query(0, 0, n - 1, idx);
    }
};

class Solution {
public:
    vector<int> minInterval(vector<vector<int>>& intervals, vector<int>& queries) {
        vector<int> points;

        for (const auto& interval : intervals) {
            points.push_back(interval[0]);
            points.push_back(interval[1]);
        }
        for (int q : queries) {
            points.push_back(q);
        }

        sort(points.begin(), points.end());
        points.erase(unique(points.begin(), points.end()), points.end());

        // compress the coordinates
        unordered_map<int, int> compress;
        for (int i = 0; i < points.size(); ++i) {
            compress[points[i]] = i;
        }

        SegmentTree segTree(points.size());

        for (const auto& interval : intervals) {
            int start = compress[interval[0]];
            int end = compress[interval[1]];
            int len = interval[1] - interval[0] + 1;
            segTree.update(start, end, len);
        }

        vector<int> ans;
        for (int q : queries) {
            int idx = compress[q];
            int res = segTree.query(idx);
            ans.push_back(res == INT_MAX ? -1 : res);
        }

        return ans;
    }
};
Source and license

Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.

Check the explanation on LeetCode Watch NeetCode on YouTube

Your recall check is in progress. Write your attempt before revealing the explanation.

Resume recall check

Browse all problem explanations