java_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.

Examples

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 <= 105
• 1 <= queries.length <= 105
• intervals[i].length == 2
• 1 <= lefti <= righti <= 107
• 1 <= queries[j] <= 107

解析

給定一個 2D 陣列 intervals

每個 intervals[i] = [ $left_i, right_i$ ] 代表某個區間 $left_i$ ≤ values ≤ $right_i$

給定一個整數陣列 queries

每個 queries[j] 代表要找的值

對於每個 queries[j] 希望找到一個 intervals[i] = [ $left_i, right_i$ ] 使得 $left_i$ ≤ values ≤ $right_i$

且讓 query_size[j] = intervals[i][1] - intervals[i][0] + 1 最小

題目要求一個演算法 找出給定的 intervals, queries 中所有 query_size 的最小值

另外當 queries[i] 找不到符合的 intervals[j] 則 query_size[i] = -1

這題的困難點在於如何有系統的去找出所有可能的 intervals 並找出最小值

要有順序性的找尋

可以透過把 intervals 根據 $left_i$ 來做由小到大的排序

有這樣的排序後就可以知道當遇到一個不符合的 intervals 時 ， 其後面的 intervals 都可以不需要再比

同樣地，把 queries 做由小到大的排序

也可以讓 queries[i] 利用之前 ≤ queries[i] 值來做減少搜尋的部份

然而要真找到 size 最小的 interval

需要利用 一個 MinHeap 把 size 跟 left 做由小到大的排序

這樣每次先把有可能的 interval 放入 minHeap

然後當發現 minHeap 最小值 < queries[i]

則 把 minHeap 掉直到 有 right ≥ queries

這樣的話, 就可以透過時間複雜度 O(nlogn + qlogq) 來做運算 其中 n = len(interval), q = len(queries)

空間複雜度 O(n+q) 因為需要把所有 interval 放入 MinHeap 還有儲存每個 queries[i] 的最小區間大小

程式碼

import java.util.*;

public class Solution {
  static class Record {
    final int size, right;
    Record(int size, int right) {
      this.size = size;
      this.right = right;
    }
  }
  public int[] minInterval(int[][] intervals, int[] queries) {
    Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));
    int qLen = queries.length;
    int nLen = intervals.length;
    int[] copyQueries = Arrays.copyOf(queries, qLen);
    Arrays.sort(copyQueries);
    HashMap<Integer, Integer> hash = new HashMap<>();
    PriorityQueue<Record> pq = new PriorityQueue<>((a, b) -> (a.size == b.size) ? a.right - b.right: a.size - b.size);
    int[] result = new int[qLen];
    int pos = 0;
    for (int q : copyQueries) {
      while(pos < nLen && intervals[pos][0] <= q) {
        pq.add(new Record(intervals[pos][1] - intervals[pos][0]+1, intervals[pos][1]));
        pos++;
      }
      while(pq.size()>0 && pq.peek().right < q) {
        pq.poll();
      }
      if (pq.isEmpty()) {
        hash.put(q, -1);
      } else {
        hash.put(q, pq.peek().size);
      }
    }
    for (int idx = 0; idx < qLen; idx++) {
      result[idx] = hash.get(queries[idx]);
    }
    return result;
  }
}

困難點

1. 需要想出有系統性找尋最小區間 size 的方式
2. 透過排除法來讓 搜訊範圍變小
3. 目前的找法並非很直覺

Solve Point

• 需要建立一個新的陣列 bufferQueries 來複製 queries
• 建立一個 hashTable hash 來儲存每個 queries 的最小區間大小
• 對 bufferQueries做排序, 對intervals 做以left 排序
• 初始化 pos = 0 代表目前查找到的最後 intervals index, pq = MinHeap
• 由小到大對每個 bufferQueries 內的值 q 做以下檢查
• while pos ≤ len(intervals) && intervals[pos][0] ≤ q, 則 更新 把 size = intervals[pos][1] - intervals[pos][0] + 1, right = intervals[pos][1] 放入 pq
• while pq.Len() > 0 && pq[0].right < q, 則更 把 pq pop 出目前最小的值
• if pq.Len() > 0 則 hash[q] = pq[0].size , 否則 -1
• 當跑完所有 queries 回傳所有對應 queries 的 sizes