Minimum Interval to Include Each Query LeetCode solution in C++

1
class Solution {
2
 public:
3
  void update(int *tree, int *lazy, int treeidx, int left, int right, int lo, int hi, int val) {
4
    int lidx = 2 * treeidx + 1;
5
    int ridx = 2 * treeidx + 2;
6
    int mid = (lo + hi) / 2;
7
    if (lazy[treeidx] != INT_MAX) {
8
      if (lazy[treeidx] < tree[treeidx]) {
9
        tree[treeidx] = lazy[treeidx];
10
        if (lo != hi) {
11
          lazy[lidx] = min(lazy[treeidx], lazy[lidx]);
12
          lazy[ridx] = min(lazy[treeidx], lazy[ridx]);
13
        }
14
      }
15
      lazy[treeidx] = INT_MAX;
16
    }
17

18
    // completely outside
19
    if (lo > right || hi < left) {
20
      return;
21
    }
22
    // completely inside
23
    if (lo >= left && hi <= right) {
24
      lazy[treeidx] = min(lazy[treeidx], val);
25
      return;
26
    }
27
    // partial
28
    update(tree, lazy, lidx, left, right, lo, mid, val);
29
    update(tree, lazy, ridx, left, right, mid + 1, hi, val);
30
  }
31

32
  int query(int *tree, int *lazy, int treeidx, int lo, int hi, int idx) {
33
    int lidx = 2 * treeidx + 1;
34
    int ridx = 2 * treeidx + 2;
35
    int mid = (lo + hi) / 2;
36
    if (lazy[treeidx] != INT_MAX) {
37
      if (lazy[treeidx] < tree[treeidx]) {
38
        tree[treeidx] = lazy[treeidx];
39
        if (lo != hi) {
40
          lazy[lidx] = min(lazy[treeidx], lazy[lidx]);
41
          lazy[ridx] = min(lazy[treeidx], lazy[ridx]);
42
        }
43
      }
44
      lazy[treeidx] = INT_MAX;
45
    }
46
    if (lo == hi) {
47
      return tree[treeidx];
48
    }
49
    if (idx <= mid) {
50
      return query(tree, lazy, lidx, lo, mid, idx);
51
    } else {
52
      return query(tree, lazy, ridx, mid + 1, hi, idx);
53
    }
54
  }
55
  vector<int> minInterval(vector<vector<int>> &intervals, vector<int> &queries) {
56
    int n = 0;
57
    for (int i = 0; i < intervals.size(); i++) {
58
      n = max(n, intervals[i][1]);
59
    }
60
    for (int i = 0; i < queries.size(); i++) {
61
      n = max(n, queries[i]);
62
    }
63
    n++;
64
    int *tree = new int[4 * n];
65
    int *lazy = new int[4 * n];
66
    for (int i = 0; i < 4 * n; i++) {
67
      tree[i] = INT_MAX;
68
      lazy[i] = INT_MAX;
69
    }
70
    for (int i = 0; i < intervals.size(); i++) {
71
      int val = intervals[i][1] - intervals[i][0] + 1;
72
      update(tree, lazy, 0, intervals[i][0], intervals[i][1], 0, n - 1, val);
73
    }
74
    vector<int> ans(queries.size());
75
    for (int i = 0; i < queries.size(); i++) {
76
      int temp = query(tree, lazy, 0, 0, n - 1, queries[i]);
77
      if (temp == INT_MAX) {
78
        ans[i] = -1;
79
      } else {
80
        ans[i] = temp;
81
      }
82
    }
83

84
    delete[] tree;
85
    delete[] lazy;
86
    return ans;
87
  }
88
};