DSA problem
Minimum Interval to Include Each Query
You are given a 2D integer array intervals, where intervals[i] = [left_i, right_i] describes the i-th interval starting at left_i and ending at right_i (both inclusive). The size of an interval is right_i - left_i + 1. You are also given an integer array queries. The answer to the j-th query is the size of the smallest interval such that left_i <= queries[j] <= right_i. If no such interval exists, the answer is -1. Return an array containing the answer for each query in the original order.
A brute force solution scans every interval for every query, costing O(m * n) which is far too slow when both arrays approach 10^5 elements. The crucial insight is that we can decouple the order: queries can be sorted and answered offline, then mapped back to their original positions.
Sort the intervals by left endpoint and sort the queries in ascending order. Walk a pointer through the intervals; for each query q, push every interval with left <= q into a min-heap keyed by interval size, storing the right endpoint alongside it. Before reading the answer, pop any heap entries whose right endpoint is strictly less than q — those intervals have already ended and cannot contain the query.
After purging, the heap top is the smallest interval still covering q, or -1 if the heap is empty. Each interval is pushed and popped at most once, so the total heap work is O(n log n). Combined with sorting and binding answers back to original query indices, the overall complexity is O((n + m) log (n + m)) time and O(n) space.
Examples
intervals = [[1,4],[2,4],[3,6],[4,4]], queries = [2,3,4,5][3,3,1,4]intervals = [[2,3],[2,5],[1,8],[20,25]], queries = [2,19,5,22][2,-1,4,6]intervals = [[1,4]], queries = [0,5][-1,-1]Constraints
- 1 <= intervals.length <= 10^5
- 1 <= queries.length <= 10^5
- intervals[i].length == 2
- 1 <= left_i <= right_i <= 10^7
- 1 <= queries[j] <= 10^7
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.