Code Implementation

import heapq

def minInterval(intervals, queries):
    intervals.sort()
    queries_sorted = sorted((q, i) for i, q in enumerate(queries))
    res = [0] * len(queries)
    min_heap = []
    i = 0
    n = len(intervals)
    for q, idx in queries_sorted:
        # Add all intervals starting before or at q
        while i < n and intervals[i][0] <= q:
            start, end = intervals[i]
            heapq.heappush(min_heap, (end - start + 1, end))
            i += 1
        # Remove intervals that end before q
        while min_heap and min_heap[0][1] < q:
            heapq.heappop(min_heap)
        # The top of the heap is the smallest interval covering q
        res[idx] = min_heap[0][0] if min_heap else -1
    return res
      

#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

vector<int> minInterval(vector<vector<int>>& intervals, vector<int>& queries) {
    sort(intervals.begin(), intervals.end());
    vector<pair<int, int>> queries_sorted;
    int qn = queries.size();
    for (int i = 0; i < qn; ++i)
        queries_sorted.push_back({queries[i], i});
    sort(queries_sorted.begin(), queries_sorted.end());
    vector<int> res(qn);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> minHeap;
    int i = 0, n = intervals.size();
    for (auto& [q, idx] : queries_sorted) {
        while (i < n && intervals[i][0] <= q) {
            minHeap.push({intervals[i][1] - intervals[i][0] + 1, intervals[i][1]});
            ++i;
        }
        while (!minHeap.empty() && minHeap.top().second < q)
            minHeap.pop();
        res[idx] = minHeap.empty() ? -1 : minHeap.top().first;
    }
    return res;
}
      

import java.util.*;

public class Solution {
    public int[] minInterval(int[][] intervals, int[] queries) {
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
        int n = queries.length;
        int[] res = new int[n];
        int[][] queryWithIdx = new int[n][2];
        for (int i = 0; i < n; i++) {
            queryWithIdx[i][0] = queries[i];
            queryWithIdx[i][1] = i;
        }
        Arrays.sort(queryWithIdx, (a, b) -> Integer.compare(a[0], b[0]));
        PriorityQueue<int[]> minHeap = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));
        int i = 0, m = intervals.length;
        for (int[] q : queryWithIdx) {
            int query = q[0], idx = q[1];
            while (i < m && intervals[i][0] <= query) {
                minHeap.offer(new int[]{intervals[i][1] - intervals[i][0] + 1, intervals[i][1]});
                i++;
            }
            while (!minHeap.isEmpty() && minHeap.peek()[1] < query)
                minHeap.poll();
            res[idx] = minHeap.isEmpty() ? -1 : minHeap.peek()[0];
        }
        return res;
    }
}
      

function minInterval(intervals, queries) {
    intervals.sort((a, b) => a[0] - b[0]);
    let queriesSorted = queries.map((q, i) => [q, i]).sort((a, b) => a[0] - b[0]);
    let res = Array(queries.length);
    let minHeap = [];
    let i = 0, n = intervals.length;
    const pushHeap = (heap, item) => {
        heap.push(item);
        let idx = heap.length - 1;
        while (idx > 0) {
            let parent = Math.floor((idx - 1) / 2);
            if (heap[parent][0] <= heap[idx][0]) break;
            [heap[parent], heap[idx]] = [heap[idx], heap[parent]];
            idx = parent;
        }
    };
    const popHeap = (heap) => {
        if (heap.length === 1) return heap.pop();
        let top = heap[0];
        heap[0] = heap.pop();
        let idx = 0, len = heap.length;
        while (true) {
            let left = 2 * idx + 1, right = 2 * idx + 2, minIdx = idx;
            if (left < len && heap[left][0] < heap[minIdx][0]) minIdx = left;
            if (right < len && heap[right][0] < heap[minIdx][0]) minIdx = right;
            if (minIdx === idx) break;
            [heap[minIdx], heap[idx]] = [heap[idx], heap[minIdx]];
            idx = minIdx;
        }
        return top;
    };
    for (let [q, idx] of queriesSorted) {
        while (i < n && intervals[i][0] <= q) {
            pushHeap(minHeap, [intervals[i][1] - intervals[i][0] + 1, intervals[i][1]]);
            i++;
        }
        while (minHeap.length && minHeap[0][1] < q) popHeap(minHeap);
        res[idx] = minHeap.length ? minHeap[0][0] : -1;
    }
    return res;
}
      

Problem Description

You are given a list of intervals, where each interval is represented by a pair [start, end], and a list of queries. For each query value q in queries, you need to find the length of the smallest interval from intervals that includes q (i.e., start <= q <= end). If no interval contains q, return -1 for that query.

Key constraints:

• Each interval can be used for multiple queries; intervals are not "used up" after one query.
• There may be multiple intervals containing a query; you must find the one with the smallest length.
• Return an array with the result for each query, in the same order as the input queries.

Thought Process

The most straightforward way to solve the problem is to, for each query, check every interval to see if it contains the query, and keep track of the one with the smallest length. However, this brute-force approach is very slow if the number of intervals and queries are large, because it would require checking all intervals for each query.

To optimize, we notice that:

• If we process queries in sorted order, we can "sweep" through the intervals and add only those intervals that could possibly contain the current query.
• By using a min-heap (priority queue), we can quickly find the smallest interval that covers the current query.
• We can remove intervals from the heap if their end is less than the current query, as they cannot cover any future queries.

Solution Approach

Let's break down the optimized algorithm step-by-step:

1. Sort the intervals by their start value.
   • This allows us to process intervals in order, adding them to our "active" set as we sweep through queries.
2. Sort the queries, but remember their original indices.
   • Sorting queries allows us to process them in ascending order, which matches how we process intervals.
   • We store the original index so we can place the answer in the correct spot in the result array.
3. Use a min-heap (priority queue) to keep track of candidate intervals.
   • For each query, we add to the heap all intervals that start before or at the query value.
   • We store intervals in the heap as (length, end) pairs so the smallest length is always on top.
   • Before answering the current query, we remove from the heap any intervals whose end is less than the query value, as they can't cover the query.
4. For each query, the top of the heap (if not empty) is the smallest interval containing the query.
   • If the heap is empty, it means no interval covers the query, so we return -1 for that query.
5. Place the answer for each query at its original index in the result array.

This approach ensures we only process each interval and query once, and we efficiently keep track of the best interval for each query.

Example Walkthrough

Suppose intervals = [[1,4],[2,4],[3,6],[4,4]] and queries = [2,3,4,5].

1. Sorting:
   • Intervals (already sorted by start): [[1,4],[2,4],[3,6],[4,4]]
   • Queries with indices: [(2,0),(3,1),(4,2),(5,3)]
2. Processing query 2:
   • Add intervals starting at or before 2: [1,4] and [2,4]
   • Heap: [(4,4), (3,4)] (length, end)
   • Both intervals cover 2. Smallest length is 3 (from [2,4])
   • Result: res[0] = 3
3. Processing query 3:
   • Add [3,6]: Heap now [(4,4), (3,4), (4,6)]
   • All intervals in heap cover 3. Smallest length is 3
   • Result: res[1] = 3
4. Processing query 4:
   • Add [4,4]: Heap now [(4,4), (3,4), (4,6), (1,4)]
   • All intervals in heap cover 4. Smallest length is 1 (from [4,4])
   • Result: res[2] = 1
5. Processing query 5:
   • Remove intervals whose end < 5: [1,4], [3,4], [4,4], [4,4] all have end=4, so are removed.
   • Only [3,6] remains, which covers 5 with length 4
   • Result: res[3] = 4

Final result: [3,3,1,4]

Time and Space Complexity

Brute-force approach:

• For each query, check all intervals: O(Q * N), where Q is the number of queries and N is the number of intervals.
• Very slow for large inputs.

• Sorting intervals: O(N log N)
• Sorting queries: O(Q log Q)
• Each interval and query is processed once. Each heap operation is O(log N).
• Total time: O(N log N + Q log Q + (N + Q) log N)
• Space: O(N) for the heap and O(Q) for the result array.

The optimized approach is much faster and feasible for large inputs.

Summary

The key to efficiently solving the "Minimum Interval to Include Each Query" problem is to process both intervals and queries in sorted order, and use a min-heap to quickly find the smallest interval covering each query. This avoids the inefficiency of brute-force checking and leverages efficient data structures for fast lookups and removals. The algorithm is elegant because it only processes each element once and maintains only the necessary candidates in the heap at each step.