Minimum Interval to Include Each Query

Hard Top 250

Associated Patterns

Interviewed At (Company Tags)

GoogleAmazon

Problem Description

You are given a 2D integer array intervals, where intervals[i] = [lefti, righti] describes the ith interval. You are also given an integer array queries.

The size of an interval is defined as righti - lefti + 1. The minimum interval to include a query queries[j] is the interval i that contains queries[j] (i.e. lefti ≤ queries[j] ≤ righti) and has the minimum size. If no such interval exists, the answer is -1.

Return an array answer containing the answers to the queries.

Examples

Example 1:

Input: intervals = [[1,4],[2,4],[3,6],[4,4]], queries = [2,3,4,5] Output: [3,3,1,4] Explanation:

Query 2: [2,4] is the smallest interval containing 2 (size 3).
Query 3: [2,4] is the smallest interval containing 3 (size 3).
Query 4: [4,4] is the smallest interval containing 4 (size 1).
Query 5: [3,6] is the smallest interval containing 5 (size 4).

Constraints

1 ≤ intervals.length, queries.length ≤ 10⁵
intervals[i].length == 2
1 ≤ lefti ≤ righti ≤ 10⁷
1 ≤ queries[j] ≤ 10⁷

Offline Processing: Sort Queries and Intervals

Answering queries in their original order requires scanning all intervals every time, costing O(Q * N), which is too slow.

Instead, process queries offline:

Sort queries in ascending order, keeping track of their original indices.
Sort intervals in ascending order by start point.
Use a min-heap to store active intervals, sorted by size: [size, right].

As we iterate through the sorted queries:

Push all intervals whose start point left is ≤ query into the heap.
Pop all intervals from the heap whose end point right is < query (they are too far left to contain this query or any subsequent sorted queries).
The top of the heap is the smallest active interval. Store its size at the query’s original index. If the heap is empty, store -1.

Solution: Offline Sweep-Line + Min-Heap

import java.util.*;

class Solution {
    public int[] minInterval(int[][] intervals, int[] queries) {
        int n = intervals.length, q = queries.length;

        // sort intervals by start point
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));

        // pair queries with their original index, then sort by query value
        int[][] sortedQueries = new int[q][2];
        for (int i = 0; i < q; i++) {
            sortedQueries[i][0] = queries[i];
            sortedQueries[i][1] = i;
        }
        Arrays.sort(sortedQueries, (a, b) -> Integer.compare(a[0], b[0]));

        // min-heap: [size, rightBound]
        PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));

        int[] result = new int[q];
        int intervalIdx = 0;

        for (int i = 0; i < q; i++) {
            int queryVal = sortedQueries[i][0];
            int origIdx = sortedQueries[i][1];

            // add all intervals that start before or at the query value
            while (intervalIdx < n && intervals[intervalIdx][0] <= queryVal) {
                int left = intervals[intervalIdx][0];
                int right = intervals[intervalIdx][1];
                heap.offer(new int[]{right - left + 1, right});
                intervalIdx++;
            }

            // remove all intervals that end before the query value
            while (!heap.isEmpty() && heap.peek()[1] < queryVal) {
                heap.poll();
            }

            if (heap.isEmpty()) {
                result[origIdx] = -1;
            } else {
                result[origIdx] = heap.peek()[0];
            }
        }

        return result;
    }
}

import heapq

class Solution:
    def minInterval(self, intervals: list[list[int]], queries: list[int]) -> list[int]:
        # sort intervals by start point
        intervals.sort()

        # sort queries but preserve original index
        sorted_queries = sorted((q, i) for i, q in enumerate(queries))

        heap = []  # (size, right_bound)
        result = [-1] * len(queries)
        i = 0
        n = len(intervals)

        for query_val, orig_idx in sorted_queries:
            # add all intervals starting at or before query
            while i < n and intervals[i][0] <= query_val:
                left, right = intervals[i]
                heapq.heappush(heap, (right - left + 1, right))
                i += 1

            # remove all intervals ending before query
            while heap and heap[0][1] < query_val:
                heapq.heappop(heap)

            if heap:
                result[orig_idx] = heap[0][0]

        return result

#include <vector>
#include <queue>
#include <algorithm>

class Solution {
public:
    std::vector<int> minInterval(std::vector<std::vector<int>>& intervals, std::vector<int>& queries) {
        int n = intervals.size(), q = queries.size();

        std::sort(intervals.begin(), intervals.end());

        std::vector<std::pair<int, int>> sortedQueries;
        for (int i = 0; i < q; i++) {
            sortedQueries.push_back({queries[i], i});
        }
        std::sort(sortedQueries.begin(), sortedQueries.end());

        // min-heap: {size, rightBound}
        using T = std::pair<int, int>;
        std::priority_queue<T, std::vector<T>, std::greater<T>> heap;

        std::vector<int> result(q, -1);
        int intervalIdx = 0;

        for (int i = 0; i < q; i++) {
            int queryVal = sortedQueries[i].first;
            int origIdx = sortedQueries[i].second;

            while (intervalIdx < n && intervals[intervalIdx][0] <= queryVal) {
                int left = intervals[intervalIdx][0];
                int right = intervals[intervalIdx][1];
                heap.push({right - left + 1, right});
                intervalIdx++;
            }

            while (!heap.empty() && heap.top().second < queryVal) {
                heap.pop();
            }

            if (!heap.empty()) {
                result[origIdx] = heap.top().first;
            }
        }

        return result;
    }
};

Complexity Analysis:

Time Complexity: O(N log N + Q log Q) where N is the number of intervals and Q is the number of queries. Sorting intervals and queries is the bottleneck. The heap operations are O((N + Q) log N) total.
Space Complexity: O(N + Q) to store queries, their indices, and heap elements.