Minimum Interval to Include Each Query

hard intervals heap offline

Problem

You are given a set of intervals, each written as [left, right] and covering every integer from left to right; the size of an interval is right − left + 1. You are also given a list of integer queries.

For every query q, report the size of the smallest interval that contains q (left ≤ q ≤ right), or −1 if no interval contains it. Answers must come back in the original query order.

Inputintervals = [[1,4],[2,4],[3,6],[4,4]], queries = [2,3,4,5]

Output[3,3,1,4]

Query 2 fits in [1,4] (size 4) and [2,4] (size 3), so the smallest is 3; query 4 fits in the tiny [4,4] (size 1); query 5 only fits in [3,6] (size 4).

intervals (JSON, [l,r] pairs)

queries (comma-separated)

import heapq

def min_interval(intervals, queries):
    intervals.sort()
    order = sorted(range(len(queries)), key=lambda j: queries[j])
    ans = [-1] * len(queries)
    heap = []  # (size, right)
    i = 0
    for j in order:
        q = queries[j]
        while i < len(intervals) and intervals[i][0] <= q:
            l, r = intervals[i]
            heapq.heappush(heap, (r - l + 1, r))
            i += 1
        while heap and heap[0][1] < q:
            heapq.heappop(heap)
        if heap:
            ans[j] = heap[0][0]
    return ans

function minInterval(intervals, queries) {
  intervals.sort((a, b) => a[0] - b[0]);
  const order = queries.map((q, j) => j).sort((a, b) => queries[a] - queries[b]);
  const ans = new Array(queries.length).fill(-1);
  const heap = []; // [size, right], min-heap keyed by size
  const less = (a, b) => heap[a][0] < heap[b][0];
  const swap = (a, b) => { [heap[a], heap[b]] = [heap[b], heap[a]]; };
  const push = (v) => {
    heap.push(v);
    for (let k = heap.length - 1; k > 0 && less(k, (k - 1) >> 1); k = (k - 1) >> 1) swap(k, (k - 1) >> 1);
  };
  const pop = () => {
    swap(0, heap.length - 1); heap.pop();
    for (let k = 0, m = 0; ; k = m) {
      if (2 * k + 1 < heap.length && less(2 * k + 1, m)) m = 2 * k + 1;
      if (2 * k + 2 < heap.length && less(2 * k + 2, m)) m = 2 * k + 2;
      if (m === k) return;
      swap(k, m);
    }
  };
  let i = 0;
  for (const j of order) {
    const q = queries[j];
    while (i < intervals.length && intervals[i][0] <= q)
      push([intervals[i][1] - intervals[i][0] + 1, intervals[i++][1]]);
    while (heap.length && heap[0][1] < q) pop();
    if (heap.length) ans[j] = heap[0][0];
  }
  return ans;
}

int[] minInterval(int[][] intervals, int[] queries) {
    Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
    Integer[] order = new Integer[queries.length];
    for (int j = 0; j < order.length; j++) order[j] = j;
    Arrays.sort(order, (a, b) -> queries[a] - queries[b]);
    int[] ans = new int[queries.length];
    Arrays.fill(ans, -1);
    PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> a[0] - b[0]);
    int i = 0;
    for (int j : order) {
        int q = queries[j];
        while (i < intervals.length && intervals[i][0] <= q) {
            int[] iv = intervals[i++];
            heap.offer(new int[]{iv[1] - iv[0] + 1, iv[1]});
        }
        while (!heap.isEmpty() && heap.peek()[1] < q) heap.poll();
        if (!heap.isEmpty()) ans[j] = heap.peek()[0];
    }
    return ans;
}

vector<int> minInterval(vector<vector<int>>& intervals, vector<int>& queries) {
    sort(intervals.begin(), intervals.end());
    vector<int> order(queries.size());
    iota(order.begin(), order.end(), 0);
    sort(order.begin(), order.end(),
         [&](int a, int b) { return queries[a] < queries[b]; });
    vector<int> ans(queries.size(), -1);
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> heap;
    size_t i = 0;
    for (int j : order) {
        int q = queries[j];
        while (i < intervals.size() && intervals[i][0] <= q) {
            heap.push({intervals[i][1] - intervals[i][0] + 1, intervals[i][1]});
            i++;
        }
        while (!heap.empty() && heap.top().second < q) heap.pop();
        if (!heap.empty()) ans[j] = heap.top().first;
    }
    return ans;
}

Explanation

Checking every interval against every query costs O(n·q). The key insight is to go offline: nothing forces us to answer queries in the given order, so we sort the queries, sweep them from smallest to largest, and write each answer back into its original slot.

Sort the intervals by left endpoint too. As the sweep reaches a query q, every interval with left ≤ q has "started", so a single pointer pushes each of them onto a min-heap keyed by size, storing (size, right). Because queries only grow, an interval is pushed exactly once during the whole sweep.

Before answering we pop while the heap top has right < q. Such an interval ends before the current query, and since later queries are even larger it can never contain any of them — discarding it is permanently safe. Every surviving entry has left ≤ q ≤ right, so the top of the heap is precisely the smallest interval containing q; if the heap is empty the answer is −1.

Walking the default example intervals = [[1,4],[2,4],[3,6],[4,4]], queries = [2,3,4,5]: at q=2 we push [1,4] (size 4) and [2,4] (size 3), top gives 3. At q=3 we add [3,6]; the top (size 3) still covers 3. At q=4 we push [4,4] (size 1) which becomes the new top, answer 1. At q=5 the tops [4,4], [2,4] and [1,4] all end before 5 and get popped, leaving [3,6], answer 4. Result: [3,3,1,4].

The lazy deletion is what makes this fast: each interval enters and leaves the heap at most once, so all heap work is O((n + q) log n). Together with sorting the intervals and the queries, the total time is O((n + q) log (n + q)) with O(n + q) extra space for the heap, the order array, and the answers.

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