Skip to content

1851. Minimum Interval to Include Each Query 👍

  • Time: $O(\texttt{sort}(n) + \texttt{sort}(q) + q\log n)$
  • Space: $O(n + q)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
struct T {
  int size;
  int right;
  T(int size, int right) : size(size), right(right) {}
};

class Solution {
 public:
  vector<int> minInterval(vector<vector<int>>& intervals,
                          vector<int>& queries) {
    vector<int> ans(queries.size(), -1);
    auto compare = [](const T& a, const T& b) { return a.size > b.size; };
    priority_queue<T, vector<T>, decltype(compare)> minHeap(compare);
    vector<vector<int>> qs;

    for (int i = 0; i < queries.size(); ++i)
      qs.push_back({queries[i], i});

    ranges::sort(intervals);
    ranges::sort(qs);

    int i = 0;  // intervals' index
    for (const vector<int>& q : qs) {
      while (i < intervals.size() && intervals[i][0] <= q[0]) {
        minHeap.emplace(intervals[i][1] - intervals[i][0] + 1, intervals[i][1]);
        ++i;
      }
      while (!minHeap.empty() && minHeap.top().right < q[0])
        minHeap.pop();
      if (!minHeap.empty())
        ans[q[1]] = minHeap.top().size;
    }

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class T {
  public int size;
  public int right;
  public T(int size, int right) {
    this.size = size;
    this.right = right;
  }
}

class Solution {
  public int[] minInterval(int[][] intervals, int[] queries) {
    int[] ans = new int[queries.length];
    Arrays.fill(ans, -1);
    Queue<T> minHeap = new Queue<T>((a, b) -> a.size - b.size);
    Integer[] indices = new Integer[queries.length];

    for (int i = 0; i < queries.length; ++i)
      indices[i] = i;

    Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
    Arrays.sort(indices, (a, b) -> queries[a] - queries[b]);

    int i = 0; // intervals' index
    for (final int index : indices) {
      while (i < intervals.length && intervals[i][0] <= queries[index]) {
        minHeap.offer(new T(intervals[i][1] - intervals[i][0] + 1, intervals[i][1]));
        ++i;
      }
      while (!minHeap.isEmpty() && minHeap.peek().right < queries[index])
        minHeap.poll();
      if (!minHeap.isEmpty())
        ans[index] = minHeap.peek().size;
    }

    return ans;
  }
}