Minimum Interval to Include Each Query — Problem & Solution
Minimum Interval to Include Each Query solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.
Minimum Interval to Include Each Query is a hard coding problem on arrays, sorting and binary search, asked in Amazon and Google interviews.
- Difficulty: Hard
- Topics: Arrays, Sorting, Binary Search, Heap
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Each intervals[i] = [left, right] covers the integers from left to right, both included; its size is right - left + 1.
For every queries[j], find the smallest size of an interval that contains the value queries[j] (left <= queries[j] <= right). If no interval contains it, the answer is -1.
Return the answers as an array in the order of queries.
Example 1
Input: intervals = [[2,5],[4,4],[6,9],[1,10]], queries = [4,3,8,11]
Output: [1,4,4,-1]
Explanation: 4 lies in [4,4] (size 1); 3 in [2,5] (size 4); 8 in [6,9] (size 4); nothing reaches 11.
Example 2
Input: intervals = [[1,3],[3,7]], queries = [3,1,9]
Output: [3,3,-1]
Constraints
1 <= intervals.length <= 10^51 <= queries.length <= 10^5intervals[i].length == 21 <= left <= right <= 10^71 <= queries[j] <= 10^7
Hints for Minimum Interval to Include Each Query
Hint 1
Answering queries in increasing order lets you reuse work: an interval that has started for one query has started for all later ones.
Hint 2
Sort intervals by
leftand add each to a pool once itsleftis at most the current query.Hint 3
Keep the pool in a min-heap by size; before reading the top, discard tops whose
rightis already below the query — they can never contain a later query either.
How to solve Minimum Interval to Include Each Query
Process the queries offline in increasing order. Intervals enter a min-heap (keyed by size) as soon as they start, and leave it lazily once they end — for sorted queries an ended interval stays ended, so throwing it away is safe.
Approach
- Sort the intervals by
left, and sort the query indices by query value. - For each query
qin that order, push every not-yet-pushed interval withleft <= qinto a min-heap keyed by(size, right). - Pop the top while its
right < q. - The answer for
qis the top's size, or-1if the heap is empty; store it at the query's original index.
Why it works
When q is answered, the heap holds every interval with left <= q except some with right < q' for an earlier q' <= q, which cannot contain q. After popping, the top has right >= q and left <= q, so it contains q, and its size is minimal among all heap members — in particular among all intervals containing q, since none of those was discarded.
Complexity
- Time —
O(n log n + m log m) - Space —
O(n + m)
Pitfalls
- Answers must come back in the original query order — sort indices, not the values themselves.
- Only the top is checked for expiry; that is enough because a stale entry deeper down is popped the moment it surfaces.
- Both ends are inclusive: the size is
right - left + 1and an interval withright == qstill counts.
Reference solution
Python
from typing import List
import heapq
def minInterval(intervals: List[List[int]], queries: List[int]) -> List[int]:
ivs = sorted(intervals)
order = sorted(range(len(queries)), key=lambda j: queries[j])
ans = [-1] * len(queries)
heap = [] # (size, right) of started intervals
at = 0
for j in order:
q = queries[j]
while at < len(ivs) and ivs[at][0] <= q:
heapq.heappush(heap, (ivs[at][1] - ivs[at][0] + 1, ivs[at][1]))
at += 1
while heap and heap[0][1] < q:
heapq.heappop(heap)
if heap:
ans[j] = heap[0][0]
return ansJava
public static int[] minInterval(int[][] intervals, int[] queries) {
int[][] ivs = intervals.clone();
Arrays.sort(ivs, (a, b) -> Integer.compare(a[0], b[0]));
Integer[] order = new Integer[queries.length];
for (int j = 0; j < queries.length; j++) order[j] = j;
Arrays.sort(order, (a, b) -> Integer.compare(queries[a], queries[b]));
// (size, right) of started intervals, smallest size on top
PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));
int[] ans = new int[queries.length];
int at = 0;
for (int j : order) {
int q = queries[j];
while (at < ivs.length && ivs[at][0] <= q) {
heap.add(new int[] { ivs[at][1] - ivs[at][0] + 1, ivs[at][1] });
at++;
}
while (!heap.isEmpty() && heap.peek()[1] < q) heap.poll();
ans[j] = heap.isEmpty() ? -1 : heap.peek()[0];
}
return ans;
}C++
vector<int> minInterval(vector<vector<int>>& intervals, vector<int>& queries) {
vector<vector<int>> ivs = intervals;
sort(ivs.begin(), ivs.end());
vector<int> order(queries.size());
for (int j = 0; j < (int) queries.size(); j++) order[j] = j;
sort(order.begin(), order.end(), [&](int a, int b) { return queries[a] < queries[b]; });
// (size, right) of started intervals, smallest size on top
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> heap;
vector<int> ans(queries.size(), -1);
size_t at = 0;
for (int j : order) {
int q = queries[j];
while (at < ivs.size() && ivs[at][0] <= q) {
heap.push({ivs[at][1] - ivs[at][0] + 1, ivs[at][1]});
at++;
}
while (!heap.empty() && heap.top().second < q) heap.pop();
if (!heap.empty()) ans[j] = heap.top().first;
}
return ans;
}JavaScript
var minInterval = function(intervals, queries) {
var ivs = intervals.slice().sort(function(a, b) { return a[0] - b[0]; });
var order = [];
for (var j = 0; j < queries.length; j++) order.push(j);
order.sort(function(a, b) { return queries[a] - queries[b]; });
var SHIFT = 16777216; // 2^24: sizes and right ends both stay below it
var heap = []; // min-heap of size * SHIFT + right
var ans = [];
for (var z = 0; z < queries.length; z++) ans.push(-1);
var at = 0;
for (var t = 0; t < order.length; t++) {
var q = queries[order[t]];
while (at < ivs.length && ivs[at][0] <= q) {
heapPush(heap, (ivs[at][1] - ivs[at][0] + 1) * SHIFT + ivs[at][1]);
at++;
}
while (heap.length > 0 && heap[0] % SHIFT < q) heapPop(heap);
if (heap.length > 0) ans[order[t]] = Math.floor(heap[0] / SHIFT);
}
return ans;
};
var heapPush = function(h, v) {
h.push(v);
var i = h.length - 1;
while (i > 0) {
var p = (i - 1) >> 1;
if (h[p] <= h[i]) break;
var t = h[p]; h[p] = h[i]; h[i] = t;
i = p;
}
};
var heapPop = function(h) {
var top = h[0];
var last = h.pop();
if (h.length > 0) {
h[0] = last;
var j = 0;
for (;;) {
var l = 2 * j + 1, r = l + 1, s = j;
if (l < h.length && h[l] < h[s]) s = l;
if (r < h.length && h[r] < h[s]) s = r;
if (s === j) break;
var t = h[s]; h[s] = h[j]; h[j] = t;
j = s;
}
}
return top;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Sorting Algorithms