Question

1851. Minimum Interval to Include Each Query

中文文档

Description

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

Solutions

Solution 1: Sorting + Offline Query + Priority Queue (Min Heap)

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 \times \log n + m \times \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:
  def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:
    n, m = len(intervals), len(queries)
    intervals.sort()
    queries = sorted((x, i) for i, x in enumerate(queries))
    ans = [-1] * m
    pq = []
    i = 0
    for x, j in queries:
      while i < n and intervals[i][0] <= x:
        a, b = intervals[i]
        heappush(pq, (b - a + 1, b))
        i += 1
      while pq and pq[0][1] < x:
        heappop(pq)
      if pq:
        ans[j] = pq[0][0]
    return ans

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;
  }
}

class Solution {
public:
  vector<int> minInterval(vector<vector<int>>& intervals, vector<int>& queries) {
    int n = intervals.size(), m = queries.size();
    sort(intervals.begin(), intervals.end());
    using pii = pair<int, int>;
    vector<pii> qs;
    for (int i = 0; i < m; ++i) {
      qs.emplace_back(queries[i], i);
    }
    sort(qs.begin(), qs.end());
    vector<int> ans(m, -1);
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    int i = 0;
    for (auto& [x, j] : qs) {
      while (i < n && intervals[i][0] <= x) {
        int a = intervals[i][0], b = intervals[i][1];
        pq.emplace(b - a + 1, b);
        ++i;
      }
      while (!pq.empty() && pq.top().second < x) {
        pq.pop();
      }
      if (!pq.empty()) {
        ans[j] = pq.top().first;
      }
    }
    return ans;
  }
};

func minInterval(intervals [][]int, queries []int) []int {
  n, m := len(intervals), len(queries)
  sort.Slice(intervals, func(i, j int) bool { return intervals[i][0] < intervals[j][0] })
  qs := make([][2]int, m)
  ans := make([]int, m)
  for i := range qs {
    qs[i] = [2]int{queries[i], i}
    ans[i] = -1
  }
  sort.Slice(qs, func(i, j int) bool { return qs[i][0] < qs[j][0] })
  pq := hp{}
  i := 0
  for _, q := range qs {
    x, j := q[0], q[1]
    for i < n && intervals[i][0] <= x {
      a, b := intervals[i][0], intervals[i][1]
      heap.Push(&pq, pair{b - a + 1, b})
      i++
    }
    for len(pq) > 0 && pq[0].r < x {
      heap.Pop(&pq)
    }
    if len(pq) > 0 {
      ans[j] = pq[0].v
    }
  }
  return ans
}

type pair struct{ v, r int }
type hp []pair

func (h hp) Len() int       { return len(h) }
func (h hp) Less(i, j int) bool { return h[i].v < h[j].v }
func (h hp) Swap(i, j int)    { h[i], h[j] = h[j], h[i] }
func (h *hp) Push(v any)    { *h = append(*h, v.(pair)) }
func (h *hp) Pop() any      { a := *h; v := a[len(a)-1]; *h = a[:len(a)-1]; return v }