15% off all plans & roadmaps Use code
See plans
Editorial
Core insight
Minimum Interval to Include Each Query · Heap (Priority Queue) Patterns
Core Insight for Minimum Interval to Include Each Query
The key observation is that query values can be processed in sorted order without changing the required output order.
For a current query q:
- Every interval with
left <= qhas become eligible to be considered. - Any interval with
right < qis no longer able to containq. - Among the remaining intervals, the answer is the interval with the smallest size.
The algorithm therefore maintains a heap of candidate intervals. Each heap entry contains:
(interval size, right endpoint)The heap is ordered by interval size. This means the top entry is the smallest interval among all currently stored candidates.
The main invariant is:
Before answering a sorted query
q, the heap contains every previously introduced interval that may still containq, while intervals whose right endpoint is smaller thanqare removed before selection.
Intervals are introduced only once because the interval pointer moves forward through intervals sorted by left endpoint. As query values increase, an interval can transition through three states:
- Not yet eligible because
left > q. - Active because
left <= q <= right. - Expired because
right < q.
Visual Description
The sorted interval list is scanned from left to right as the sorted query values increase. At each query position, intervals whose left endpoints have crossed the query are inserted into the min-heap. The heap contains active and possibly expired intervals until the cleanup phase removes entries whose right endpoints lie before the query. The heap root then identifies the minimum-size active interval.
Deep dive
Full breakdown
Full reasoning, pitfalls, and implementation flow
LeetCode 1851: Minimum Interval to Include Each Query Solution & Explanation
Problem Overview
TL;DR: Sort intervals by their left endpoint, process queries in increasing order, and use a min-heap to keep the currently active interval with the smallest size.
In LeetCode 1851: Minimum Interval to Include Each Query, each interval [l, r] contains every integer from l through r, with size r - l + 1. For every query, return the size of the smallest interval that contains it. If no interval contains the query, return -1.
The answer must remain aligned with the original query order, including duplicate queries. This makes the problem a popular interview question involving sorting, greedy selection, and priority queues. The LeetCode 1851 Solution below provides the optimal solution for interviews.
Brute Force Approach for Minimum Interval to Include Each Query
A direct approach checks every interval independently for every query:
- For each query, scan all intervals.
- If an interval satisfies
left <= query <= right, calculate its size. - Keep the smallest qualifying size.
- Store
-1if no interval contains the query.
Naive Pseudocode
answer = array filled with -1
for each query at index i:
bestSize = infinity
for each interval [left, right]:
if left <= query <= right:
size = right - left + 1
bestSize = min(bestSize, size)
if bestSize is not infinity:
answer[i] = bestSize
return answerComplexity
Let:
nbe the number of intervalsmbe the number of queries
Each query examines every interval, so the time complexity is:
O(n * m)With both arrays allowed to contain up to 10^5 elements, this can require up to 10^10 interval checks. That exceeds practical limits and results in Time Limit Exceeded.
The brute force method also repeats the same interval comparisons for nearby queries, even though sorted query values could allow the work to be shared.
Algorithm Strategy: Heap (Priority Queue) Patterns
- Sort intervals by their left endpoint.
- Create pairs containing each query value and its original index.
- Sort these query pairs by query value.
- Initialize a min-heap ordered by interval size.
- For each query in sorted order:
- Insert every interval whose left endpoint is at most the query.
- Remove heap entries whose right endpoint is smaller than the query.
- If the heap is non-empty, use its top interval size as the answer for the query's original index.
- Return the result array.
The sorted query pairs preserve the original positions, so processing order can change without changing the required output order.
Execution Flow
For each query in ascending order:
- Read the query value and its original position.
- Advance the interval pointer while the next interval has
left <= query. - For every newly reached interval:
- Compute
right - left + 1. - Insert
(size, right)into the min-heap.
- Compute
- Repeatedly inspect the heap top:
- If its right endpoint is less than the current query, remove it.
- Continue until the heap is empty or its top interval still reaches the query.
- If the heap contains an interval, assign its top size to the original query position.
- If the heap is empty, leave the answer as
-1.
Duplicate query values are processed independently. They may produce the same answer, but each original index receives its own result.
Proof of Correctness
Consider a query value q during sorted processing.
All possible intervals are inserted
Intervals are sorted by left endpoint. The interval pointer inserts every interval satisfying:
left <= qTherefore, every interval that could contain q has been inserted before the answer is selected.
Invalid intervals are removed
An inserted interval cannot contain q if:
right < qThe cleanup loop removes exactly these expired intervals. Any interval remaining in the heap satisfies:
left <= q
right >= qThus, every remaining heap entry contains q.
The heap selects the smallest valid interval
The heap is ordered by interval size. After expired intervals are removed, every remaining entry represents a valid interval containing q. Therefore, the heap top has the minimum size among all valid intervals.
If no entries remain, no interval contains q, so -1 is correct.
Since this reasoning holds for every sorted query, and each result is written to its original query index, the algorithm always returns the correct answer array.
Pattern Reuse Notes
The following problems share the same pattern/subpattern:
- LeetCode 1792: Maximum Average Pass Ratio
- LeetCode 253: Meeting Rooms II
- LeetCode 857: Minimum Cost to Hire K Workers
- LeetCode 1642: Furthest Building You Can Reach
In each problem, a priority queue maintains the currently relevant choices and supports efficient greedy selection. For LeetCode 1851: Minimum Interval to Include Each Query, the heap stores active intervals and selects the minimum size. Meeting Rooms II uses a heap to track active room end times, while the other problems use a heap to repeatedly choose the best current cost or resource candidate.
Feynman coach · Before you peek at the code
Can you explain the core insight in your own words?
If you can explain it before reading code, you’re far more likely to recall it under interview pressure.
Loading your attempt…
Reference Implementation
C++ Solution for LeetCode 1851
1class Solution {
2public:
3 vector<int> minInterval(vector<vector<int>>& intervals, vector<int>& queries) {
4 sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b) {
5 return a[0] < b[0];
6 });
7
8 vector<pair<int, int>> orderedQueries;
9 orderedQueries.reserve(queries.size());
10 for (int i = 0; i < static_cast<int>(queries.size()); ++i) {
11 orderedQueries.push_back({queries[i], i});
12 }
13 sort(orderedQueries.begin(), orderedQueries.end());
14
15 priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> candidates;
16 vector<int> answer(queries.size(), -1);
17 int intervalIndex = 0;
18
19 for (const auto& query : orderedQueries) {
20 int value = query.first;
21
22 while (intervalIndex < static_cast<int>(intervals.size()) &&
23 intervals[intervalIndex][0] <= value) {
24 int left = intervals[intervalIndex][0];
25 int right = intervals[intervalIndex][1];
26 candidates.push({right - left + 1, right});
27 ++intervalIndex;
28 }
29
30 while (!candidates.empty() && candidates.top().second < value) {
31 candidates.pop();
32 }
33
34 if (!candidates.empty()) {
35 answer[query.second] = candidates.top().first;
36 }
37 }
38
39 return answer;
40 }
41};Java Solution for LeetCode 1851
1class Solution {
2 public int[] minInterval(int[][] intervals, int[] queries) {
3 java.util.Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
4
5 Integer[] queryOrder = new Integer[queries.length];
6 for (int i = 0; i < queries.length; i++) {
7 queryOrder[i] = i;
8 }
9 java.util.Arrays.sort(queryOrder, (a, b) -> Integer.compare(queries[a], queries[b]));
10
11 int[] result = new int[queries.length];
12 java.util.Arrays.fill(result, -1);
13
14 java.util.PriorityQueue<int[]> candidates = new java.util.PriorityQueue<>(
15 (a, b) -> {
16 int comparison = Integer.compare(a[0], b[0]);
17 if (comparison != 0) {
18 return comparison;
19 }
20 return Integer.compare(a[1], b[1]);
21 }
22 );
23
24 int intervalIndex = 0;
25
26 for (int queryIndex : queryOrder) {
27 int query = queries[queryIndex];
28
29 while (intervalIndex < intervals.length
30 && intervals[intervalIndex][0] <= query) {
31 int left = intervals[intervalIndex][0];
32 int right = intervals[intervalIndex][1];
33 candidates.offer(new int[] {right - left + 1, right});
34 intervalIndex++;
35 }
36
37 while (!candidates.isEmpty() && candidates.peek()[1] < query) {
38 candidates.poll();
39 }
40
41 if (!candidates.isEmpty()) {
42 result[queryIndex] = candidates.peek()[0];
43 }
44 }
45
46 return result;
47 }
48}Python Solution for LeetCode 1851
1import heapq
2from typing import List, Optional
3
4class Solution:
5 def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:
6 ordered_intervals = sorted(intervals, key=lambda interval: interval[0])
7 query_order = sorted(range(len(queries)), key=lambda index: queries[index])
8 result = [-1] * len(queries)
9 candidates = []
10 interval_index = 0
11
12 for query_index in query_order:
13 query = queries[query_index]
14
15 while (interval_index < len(ordered_intervals)
16 and ordered_intervals[interval_index][0] <= query):
17 left, right = ordered_intervals[interval_index]
18 heapq.heappush(candidates, (right - left + 1, right))
19 interval_index += 1
20
21 while candidates and candidates[0][1] < query:
22 heapq.heappop(candidates)
23
24 if candidates:
25 result[query_index] = candidates[0][0]
26
27 return result