1851. Minimum Interval to Include Each Query
You are given a 2D integer array intervals, where intervals[i] = [lefti, righti] describes the ith interval starting at lefti and ending at righti (inclusive). The size of an interval is defined as the number of integers it contains, or more formally righti - lefti + 1.
You are also given an integer array queries. The answer to the jth query is the size of the smallest interval i such that lefti <= queries[j] <= righti. If no such interval exists, the answer is -1.
Return an array containing the answers to the queries.
Example 1:
Input: intervals = [[1,4],[2,4],[3,6],[4,4]], queries = [2,3,4,5]
Output: [3,3,1,4]
Explanation: The queries are processed as follows:
- Query = 2: The interval [2,4] is the smallest interval containing 2. The answer is 4 - 2 + 1 = 3.
- Query = 3: The interval [2,4] is the smallest interval containing 3. The answer is 4 - 2 + 1 = 3.
- Query = 4: The interval [4,4] is the smallest interval containing 4. The answer is 4 - 4 + 1 = 1.
- Query = 5: The interval [3,6] is the smallest interval containing 5. The answer is 6 - 3 + 1 = 4.
Example 2:
Input: intervals = [[2,3],[2,5],[1,8],[20,25]], queries = [2,19,5,22]
Output: [2,-1,4,6]
Explanation: The queries are processed as follows:
- Query = 2: The interval [2,3] is the smallest interval containing 2. The answer is 3 - 2 + 1 = 2.
- Query = 19: None of the intervals contain 19. The answer is -1.
- Query = 5: The interval [2,5] is the smallest interval containing 5. The answer is 5 - 2 + 1 = 4.
- Query = 22: The interval [20,25] is the smallest interval containing 22. The answer is 25 - 20 + 1 = 6.
Constraints:
1 <= intervals.length <= 1051 <= queries.length <= 105intervals[i].length == 21 <= lefti <= righti <= 1071 <= queries[j] <= 107
Solution:
题读不懂系列
class Solution {
public int[] minInterval(int[][] intervals, int[] queries) {
//// Sort intervals by their start points
Arrays.sort(intervals, (a, b) -> a[0] - b[0]); // O(nlogn)
// 区间起点排序
// [1,4], [2,4], [3,6], [4,4]
// // Prepare a sorted copy of queries and their original indices
int[][] sortedQueries = new int[queries.length][2];
// [0, 0],
// [0, 0],
// [0, 0],
// [0, 0],
for (int i = 0; i < queries.length; i++){
sortedQueries[i][0] = queries[i];
sortedQueries[i][1] = i;
}
// [2,0],
// [3,1],
// [4,2],
// [5,3],
Arrays.sort(sortedQueries, (a, b) -> a[0] - b[0]);
// [2,0], [3,1],[4,2], [5,3]
PriorityQueue<int[]> pq = new PriorityQueue<int[]>((a, b) -> a[1] - b[1]);
// minheap
// // Min-heap to keep track of the smallest interval size
// O(logn)
int[] result = new int[queries.length]; //[0, 0, 0, 0]
Arrays.fill(result, -1); // [-1, -1, -1, -1]
// // Index to track the intervals
int intervalIndex = 0;
// // Process each query
for (int[] query : sortedQueries){ // [2,0], [3,1],[4,2], [5,3]
int q = query[0]; // 2
int originalIndex = query[1];// 0
// // interval [1,4], [2,4], [3,6], [4,4]
// Add all intervals that start before or at the current query
while (intervalIndex < intervals.length && intervals[intervalIndex][0] <= q){
// 0 < 4 && intervals[0][0] <= q 1 <= 2 ; 1 < 4 2<=2
int start = intervals[intervalIndex][0]; // 1 ; 2,
int end = intervals[intervalIndex][1]; // 4 ; 4
int size = end - start + 1; // 4 - 1 + 1 = 4 ; 4-2 +1 = 3
pq.offer(new int[]{end, size}); // 4,4 // {4, 3} ->
intervalIndex++; // 1, 2
}
// // Remove intervals from the heap that end before the current query
while(!pq.isEmpty() && pq.peek()[0] < q){
// {4,3},{4,4} 4 < 2 x
pq.poll();
}
// // The smallest interval containing the query (if any) is at the top of the heap
if (!pq.isEmpty()){
result[originalIndex] = pq.peek()[1];
// [3, 0 , 0, 0]
}
}
return result;
}
}
// TC: O(nlogn)
// SC: O(n)
class Solution {
public int[] minInterval(int[][] intervals, int[] queries) {
Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
//[1,8], [2,3], [2,5], [20,25]
int[][] sortedQueries = new int[queries.length][2];
// [0 , 0]
// [0 , 0]
// [0, 0]
// [0, 0]
for (int i = 0; i < queries.length; i++){
sortedQueries[i][0] = queries[i];
sortedQueries[i][1] = i;
}
// [2, 0]
// [19,1]
// [5, 2]
// [22,3]
Arrays.sort(sortedQueries, (a, b) -> a[0] - b[0]);
//[2, 0][5,2],[19,1][22,3]
PriorityQueue<int[]> pq = new PriorityQueue<int[]>((a, b) -> a[1] - b[1]);
int[] result = new int[queries.length];
Arrays.fill(result, -1);
int intervalIndex = 0;
// [1,8], [2,3], [2,5], [20,25]
for (int[] query : sortedQueries){ //[2, 0][5,2],[19,1][22,3]
int q = query[0]; // 2
int originalIndex = query[1]; // 0
while(intervalIndex < intervals.length && intervals[intervalIndex][0] <= q){
// 0 < 4 && intervals[0][0] = 1, <= 2
// 1 < 4 && intervals[1][0] 2 <= 2
// 2 < 4 && intervals[2][0] 2 <= 2
int start = intervals[intervalIndex][0]; // 0 // 2 // 2
int end = intervals[intervalIndex][1]; // 8 // 3 // 5
int size = end - start + 1; // 8-1 + 1 = 8 // 3-2 + 1= 2 // 5- 2 + 1 =4
pq.offer(new int[]{end, size}); // 8, 8 // {3, 2} //{5, 4}
intervalIndex++; // 1 // 2 // 3
}
// {3,2}, {5, 4} {8,8},
//
while(!pq.isEmpty() && pq.peek()[0] < q){
pq.poll(); //
}
if (!pq.isEmpty()){
result[originalIndex] = pq.peek()[1];
// 2
}
}
return result;
}
}
class Solution {
public int[] minInterval(int[][] intervals, int[] queries) {
Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
int[][] sortedQueries = new int[queries.length][2];
for (int i = 0; i < queries.length; i++){
sortedQueries[i][0] = queries[i];
sortedQueries[i][1] = i;
}
Arrays.sort(sortedQueries, (a, b) -> a[0] - b[0]);
PriorityQueue<int[]> pq = new PriorityQueue<int[]>((a, b) -> a[1] - b[1]);
int[] result = new int[queries.length];
Arrays.fill(result, -1);
int intervalsIndex = 0;
for (int[] query : sortedQueries){
int q = query[0];
int orignialIndex = query[1];
while(intervalsIndex < intervals.length && intervals[intervalsIndex][0] <= q){
int left = intervals[intervalsIndex][0];
int right = intervals[intervalsIndex][1];
int size = right - left + 1;
pq.offer(new int[]{right, size});
intervalsIndex++;
}
while(!pq.isEmpty() && pq.peek()[0] < q){
pq.poll();
}
if (!pq.isEmpty()){
result[orignialIndex] = pq.peek()[1];
}
}
return result;
}
}
// TC: O(nlogn)
// SC: O(n)