Minimum Interval to Include Each Query

Problem#

Given intervals and queries, for each q, return the size (end - start + 1) of the smallest interval containing q, or -1.

Examples#

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

Constraints#

1 <= intervals.length, queries.length <= 10^5.

Hints#

Hint 1

Sort intervals by start and queries ascending; activate intervals as their start ≤ q; pop expired tops.

Approach#

Sort queries by value (remember original order). Sort intervals by start. Sweep queries in order; for each query, push every interval starting ≤ q into a min-heap keyed by size; pop heap tops with end < q (expired); the top is the answer.

Solution#

class Solution {
public:
    vector<int> minInterval(vector<vector<int>>& intervals, vector<int>& queries) {
        sort(intervals.begin(), intervals.end());
        vector<pair<int,int>> qs;
        for (int i = 0; i < (int)queries.size(); ++i) qs.push_back({queries[i], i});
        sort(qs.begin(), qs.end());

        priority_queue<tuple<int,int,int>, vector<tuple<int,int,int>>, greater<>> pq;
        // (size, start, end), min-heap by size
        vector<int> ans(queries.size(), -1);
        int i = 0;
        for (auto& [q, idx] : qs) {
            while (i < (int)intervals.size() && intervals[i][0] <= q) {
                int s = intervals[i][0], e = intervals[i][1];
                pq.emplace(e - s + 1, s, e);
                ++i;
            }
            while (!pq.empty() && get<2>(pq.top()) < q) pq.pop();
            if (!pq.empty()) ans[idx] = get<0>(pq.top());
        }
        return ans;
    }
};

type intervalHeap [][3]int // (size, start, end)

func (h intervalHeap) Len() int            { return len(h) }
func (h intervalHeap) Less(i, j int) bool  { return h[i][0] < h[j][0] }
func (h intervalHeap) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *intervalHeap) Push(x interface{}) { *h = append(*h, x.([3]int)) }
func (h *intervalHeap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[:n-1]
    return x
}

func minInterval(intervals [][]int, queries []int) []int {
    sort.Slice(intervals, func(i, j int) bool { return intervals[i][0] < intervals[j][0] })
    type qi struct{ v, idx int }
    qs := make([]qi, len(queries))
    for i, q := range queries {
        qs[i] = qi{q, i}
    }
    sort.Slice(qs, func(i, j int) bool { return qs[i].v < qs[j].v })

    pq := &intervalHeap{}
    ans := make([]int, len(queries))
    for i := range ans {
        ans[i] = -1
    }
    i := 0
    for _, q := range qs {
        for i < len(intervals) && intervals[i][0] <= q.v {
            s, e := intervals[i][0], intervals[i][1]
            heap.Push(pq, [3]int{e - s + 1, s, e})
            i++
        }
        for pq.Len() > 0 && (*pq)[0][2] < q.v {
            heap.Pop(pq)
        }
        if pq.Len() > 0 {
            ans[q.idx] = (*pq)[0][0]
        }
    }
    return ans
}

from typing import List
import heapq

class Solution:
    def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:
        intervals.sort()
        qs = sorted((q, i) for i, q in enumerate(queries))
        heap = []  # (size, end)
        ans = [-1] * len(queries)
        i = 0
        for q, idx in qs:
            while i < len(intervals) and intervals[i][0] <= q:
                s, e = intervals[i]
                heapq.heappush(heap, (e - s + 1, e))
                i += 1
            while heap and heap[0][1] < q:
                heapq.heappop(heap)
            if heap:
                ans[idx] = heap[0][0]
        return ans

class MinHeap {
    constructor(cmp) { this.h = []; this.cmp = cmp; }
    size() { return this.h.length; }
    top() { return this.h[0]; }
    push(v) { this.h.push(v); this.up(this.h.length - 1); }
    pop() {
        const top = this.h[0];
        const last = this.h.pop();
        if (this.h.length) { this.h[0] = last; this.down(0); }
        return top;
    }
    up(i) {
        while (i > 0) {
            const p = (i - 1) >> 1;
            if (this.cmp(this.h[p], this.h[i]) <= 0) break;
            [this.h[p], this.h[i]] = [this.h[i], this.h[p]];
            i = p;
        }
    }
    down(i) {
        const n = this.h.length;
        while (true) {
            const l = 2 * i + 1, r = l + 1;
            let s = i;
            if (l < n && this.cmp(this.h[l], this.h[s]) < 0) s = l;
            if (r < n && this.cmp(this.h[r], this.h[s]) < 0) s = r;
            if (s === i) break;
            [this.h[s], this.h[i]] = [this.h[i], this.h[s]];
            i = s;
        }
    }
}

function minInterval(intervals, queries) {
    intervals.sort((a, b) => a[0] - b[0]);
    const qs = queries.map((q, i) => [q, i]).sort((a, b) => a[0] - b[0]);
    const heap = new MinHeap((a, b) => a[0] - b[0]); // [size, end]
    const ans = new Array(queries.length).fill(-1);
    let i = 0;
    for (const [q, idx] of qs) {
        while (i < intervals.length && intervals[i][0] <= q) {
            const [s, e] = intervals[i];
            heap.push([e - s + 1, e]);
            i++;
        }
        while (heap.size() && heap.top()[1] < q) heap.pop();
        if (heap.size()) ans[idx] = heap.top()[0];
    }
    return ans;
}

class Solution {
    public int[] minInterval(int[][] intervals, int[] queries) {
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
        int q = queries.length;
        int[][] qs = new int[q][2];
        for (int i = 0; i < q; i++) qs[i] = new int[]{queries[i], i};
        Arrays.sort(qs, (a, b) -> a[0] - b[0]);

        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]); // [size, end]
        int[] ans = new int[q];
        Arrays.fill(ans, -1);
        int i = 0;
        for (int[] qi : qs) {
            int qv = qi[0], idx = qi[1];
            while (i < intervals.length && intervals[i][0] <= qv) {
                int s = intervals[i][0], e = intervals[i][1];
                pq.offer(new int[]{e - s + 1, e});
                i++;
            }
            while (!pq.isEmpty() && pq.peek()[1] < qv) pq.poll();
            if (!pq.isEmpty()) ans[idx] = pq.peek()[0];
        }
        return ans;
    }
}

class MinHeap<T> {
    private h: T[] = [];
    constructor(private cmp: (a: T, b: T) => number) {}
    size(): number { return this.h.length; }
    top(): T { return this.h[0]; }
    push(v: T): void { this.h.push(v); this.up(this.h.length - 1); }
    pop(): T {
        const top = this.h[0];
        const last = this.h.pop()!;
        if (this.h.length) { this.h[0] = last; this.down(0); }
        return top;
    }
    private up(i: number): void {
        while (i > 0) {
            const p = (i - 1) >> 1;
            if (this.cmp(this.h[p], this.h[i]) <= 0) break;
            [this.h[p], this.h[i]] = [this.h[i], this.h[p]];
            i = p;
        }
    }
    private down(i: number): void {
        const n = this.h.length;
        while (true) {
            const l = 2 * i + 1, r = l + 1;
            let s = i;
            if (l < n && this.cmp(this.h[l], this.h[s]) < 0) s = l;
            if (r < n && this.cmp(this.h[r], this.h[s]) < 0) s = r;
            if (s === i) break;
            [this.h[s], this.h[i]] = [this.h[i], this.h[s]];
            i = s;
        }
    }
}

function minInterval(intervals: number[][], queries: number[]): number[] {
    intervals.sort((a, b) => a[0] - b[0]);
    const qs: [number, number][] = queries.map((q, i) => [q, i]);
    qs.sort((a, b) => a[0] - b[0]);
    const heap = new MinHeap<[number, number]>((a, b) => a[0] - b[0]); // [size, end]
    const ans: number[] = new Array(queries.length).fill(-1);
    let i = 0;
    for (const [q, idx] of qs) {
        while (i < intervals.length && intervals[i][0] <= q) {
            const [s, e] = intervals[i];
            heap.push([e - s + 1, e]);
            i++;
        }
        while (heap.size() && heap.top()[1] < q) heap.pop();
        if (heap.size()) ans[idx] = heap.top()[0];
    }
    return ans;
}

Editorial#

Offline (= “answer all queries with rearrangement allowed”) is the key reframing. Sorted queries let us monotonically activate intervals, never deactivating mid-stream — only popping expired ones at the top. Each interval enters and leaves the heap once → O((n + q) log (n + q)).

Complexity#

Time: O((n + q) log (n + q)).
Space: O(n + q).

Problem#

Examples#

Constraints#

Hints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Keyboard shortcuts

Problem#

Examples#

Constraints#

Hints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Related#