Minimum Interval to Include Each Query
For each query value, find the length of the smallest closed integer interval containing it. Interval length is end minus start plus one.
Work through the cases
3 examplesInput notation
Query values on line 1; interval start end pairs on subsequent lines.Expected result
One answer per query, in original order, separated by spaces. Use -1 if no interval contains it.Case 1
Input
2 5 9 1 4 4 6
Expected output
4 3 -1
Case 2
Input
3 3 3
Expected output
1
Case 3
Input
0 1 2
Expected output
-1
These notes use simplified input/output notation. The linked platform defines the method signature and judge format.
FROM IDEA TO IMPLEMENTATION
Understand the approach.
Compare the documented approaches below. Brute force, better, and optimal versions appear where available; a direct exercise may need only one approach.
Each query wants the shortest interval covering that point. Both arrays can have size 10^5, so scanning all intervals per query is impossible. Sort queries offline by coordinate and intervals by left endpoint. A min-heap stores (length,right) of intervals that already started: push those whose left is at most the query, pop those whose right is too small. The heap top is the shortest cover of the current point.
We notice that the order of queries does not affect the answer, and the intervals involved do not change. Therefore, we consider sorting all queries in ascending order, and sorting all intervals in ascending order of the left endpoint.
We use a priority queue (min heap) pq to maintain all current intervals. Each element in the queue is a pair (v, r), representing an interval with length v and right endpoint r. Initially, the priority queue is empty. In addition, we define a pointer i that points to the current interval being traversed, and initially i=0.
We traverse each query (x, j) in ascending order and perform the following operations:
- If the pointer i has not traversed all intervals, and the left endpoint of the current interval [a, b] is less than or equal to x, then we add this interval to the priority queue and move the pointer i one step forward. Repeat this process. - If the priority queue is not empty, and the right endpoint of the heap top element is less than x, then we pop the heap top element. Repeat this process. - At this point, if the priority queue is not empty, then the heap top element is the smallest interval containing x. We add its length v to the answer array ans.
After the above process is over, we return the answer array ans.
The time complexity is O(n × log n + m × log m), and the space complexity is O(n + m). Where n and m are the lengths of the arrays intervals and queries respectively.
class Solution {
public int[] minInterval(int[][] intervals, int[] queries) {
int n = intervals.length, m = queries.length;
Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
int[][] qs = new int[m][0];
for (int i = 0; i < m; ++i) {
qs[i] = new int[] {queries[i], i};
}
Arrays.sort(qs, (a, b) -> a[0] - b[0]);
int[] ans = new int[m];
Arrays.fill(ans, -1);
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
int i = 0;
for (int[] q : qs) {
while (i < n && intervals[i][0] <= q[0]) {
int a = intervals[i][0], b = intervals[i][1];
pq.offer(new int[] {b - a + 1, b});
++i;
}
while (!pq.isEmpty() && pq.peek()[1] < q[0]) {
pq.poll();
}
if (!pq.isEmpty()) {
ans[q[1]] = pq.peek()[0];
}
}
return ans;
}
}Reference code. Platform solutions may use supplied node types, imports, or collection libraries; foundational examples are complete programs.
Solutions adapted from Doocs / LeetCode contributors, licensed under CC BY-SA 4.0. Formatting changed; TypeScript versions converted to JavaScript. Supplemental implementations and approach notes added. Adapted solution material is available under the same license.