1
/*
2
    https://leetcode.com/problems/range-module/
3

4
    Idea is to use a height balanced tree to save the intervals. Intervals are
5
   kept according to the start point. We search for the position where the given
6
   range can lie, then check the previous if it overlaps and keep iterating
7
   forward while the intervals are overlapping.
8

9
    QueryRange:
10
    We first find the range of values in [left, right). Then for each of the
11
   overlapping intervals, we subtract the common range. Finally if the entire
12
   range is covered, then the range will become zero.
13
*/
14
class RangeModule {
15
 private:
16
  struct Interval {
17
    const bool operator<(const Interval &b) const {
18
      // Important to implement for == case, otherwise intervals
19
      // with same start won't exist
20
      // return start < b.start || (start == b.start && end < b.end);
21

22
      // This is the best way to compare since tuple already have ordering
23
      // implemented for fields
24
      return tie(start, end) < tie(b.start, b.end);
25
    }
26

27
    int start = -1, end = -1;
28
    Interval(int start, int end) : start(start), end(end) {};
29
  };
30

31
  set<Interval> intervals;
32

33
 public:
34
  RangeModule() {}
35

36
  // TC: Searching O(logn) + O(n) Merging, worst case when current interval
37
  // covers all, insertion would take O(1) SC: O(1)
38
  void addRange(int left, int right) {
39
    Interval interval(left, right);
40
    // Find the position where interval should lie st the next interval's
41
    // start >= left
42
    auto it = intervals.lower_bound(interval);
43

44
    // check if previous overlaps, move the iterator backwards
45
    if (!intervals.empty() && it != intervals.begin() && prev(it)->end >= interval.start) {
46
      --it;
47
      interval.start = min(it->start, interval.start);
48
    }
49

50
    // merge while intervals overlap
51
    while (it != intervals.end() && it->start <= interval.end) {
52
      interval.end = max(it->end, interval.end);
53
      intervals.erase(it++);
54
    }
55
    intervals.insert(interval);
56
  }
57

58
  // TC: Searching O(logn) + O(n) Merging, worst case when current interval
59
  // covers all SC: O(1)
60
  bool queryRange(int left, int right) {
61
    Interval interval(left, right);
62
    // Range of numbers that needs to be checked
63
    int range = right - left;
64
    // Find the position where interval should lie st the next interval's
65
    // start >= left
66
    auto it = intervals.lower_bound(interval);
67

68
    // check if previous interval overlaps the range, previous only
69
    // covers iff the open end > start of current. [prev.start, prev.end) [left,
70
    // right)
71
    if (!intervals.empty() && it != intervals.begin() && prev(it)->end > interval.start) {
72
      // remove the common portion
73
      int common = min(interval.end, prev(it)->end) - interval.start;
74
      range -= common;
75
    }
76
    // for all the following overlapping intervals, remove the common portion
77
    while (it != intervals.end() && it->start <= interval.end) {
78
      int common = min(interval.end, it->end) - it->start;
79
      range -= common;
80
      ++it;
81
    }
82
    // Check if the entire range was covered or not
83
    return range == 0;
84
  }
85

86
  // TC: Searching O(logn) + O(n) Merging, worst case when current interval
87
  // covers all SC: O(1)
88
  void removeRange(int left, int right) {
89
    Interval interval(left, right);
90
    // Find the position where interval should lie st the next interval's
91
    // start >= left
92
    auto it = intervals.lower_bound(interval);
93

94
    // check if previous overlaps, then move the iterator position backwards
95
    if (!intervals.empty() && it != intervals.begin() && prev(it)->end > interval.start) --it;
96

97
    // For each of the overlapping intervals, remove the common portions
98
    while (it != intervals.end() && it->start < interval.end) {
99
      // Start and End of common portion
100
      int common_start = max(interval.start, it->start);
101
      int common_end = min(interval.end, it->end);
102

103
      // only a section of interval overlaps, remove that part
104
      // an overlapping interval might have to be broken into two
105
      // non-overlapping parts Eg [---------------------) Bigger interval
106
      // [--------) Ongoing interval
107
      // [------) [-----) Original interval broken into left and right parts
108

109
      // check if there is some range left on the left side
110
      if (it->start < common_start) intervals.insert(Interval(it->start, common_start));
111

112
      // check if there is some range left on the right side
113
      if (it->end > common_end) intervals.insert(Interval(common_end, it->end));
114

115
      // Remove the original interval
116
      intervals.erase(it++);
117
    }
118
  }
119
};
120

121
/**
122
 * Your RangeModule object will be instantiated and called as such:
123
 * RangeModule* obj = new RangeModule();
124
 * obj->addRange(left,right);
125
 * bool param_2 = obj->queryRange(left,right);
126
 * obj->removeRange(left,right);
127
 */