leetcode 715 - Range Module

https://leetcode.com/problems/range-module/

A Range Module is a module that tracks ranges of numbers. Your task is to design and implement the following interfaces in an efficient manner.

addRange(int left, int right) Adds the half-open interval [left, right), tracking every real number in that interval. Adding an interval that partially overlaps with currently tracked numbers should add any numbers in the interval [left, right) that are not already tracked.
queryRange(int left, int right) Returns true if and only if every real number in the interval [left, right) is currently being tracked.
removeRange(int left, int right) Stops tracking every real number currently being tracked in the interval [left, right).
Example 1:
addRange(10, 20): null
removeRange(14, 16): null
queryRange(10, 14): true (Every number in [10, 14) is being tracked)
queryRange(13, 15): false (Numbers like 14, 14.03, 14.17 in [13, 15) are not being tracked)
queryRange(16, 17): true (The number 16 in [16, 17) is still being tracked, despite the remove operation)
Note:

A half open interval [left, right) denotes all real numbers left <= x < right.
0 < left < right < 10^9 in all calls to addRange, queryRange, removeRange.
The total number of calls to addRange in a single test case is at most 1000.
The total number of calls to queryRange in a single test case is at most 5000.
The total number of calls to removeRange in a single test case is at most 1000.

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
class RangeModule {
public:
RangeModule() {

}

//O(N)
void addRange(int left, int right) {
bool added = false;
vector<pair<int,int>> new_ranges;

int n = ranges.size();
int i = 0;

while (i < n || !added) {
pair<int,int> next;

if (i == n || (!added && left < ranges[i].first)) {
next = {left, right};
added = true;
} else {
next = ranges[i];
i++;
}

if (new_ranges.empty() || new_ranges.back().second < next.first)
new_ranges.push_back(next);
else
new_ranges.back().second = max(new_ranges.back().second, next.second);
}

ranges.swap(new_ranges);
}

//O(logN)
bool queryRange(int left, int right) {
int lo = 0, hi = ranges.size() - 1;

while (lo <= hi) {
int mid = lo + (hi - lo) / 2;

if (ranges[mid].first <= left)
lo = mid + 1;
else
hi = mid - 1;
}

if (lo == 0) return false;

int idx = lo - 1;
return ranges[idx].first <= left && ranges[idx].second >= right;
}

//O(N)
void removeRange(int left, int right) {
vector<pair<int,int>> new_ranges;

for (auto &range : ranges) {
if (range.first >= right || range.second <= left) {
new_ranges.push_back(range);
continue;
}

pair<int,int> left_range = {range.first, left};
if (left_range.first < left_range.second)
new_ranges.push_back(left_range);

pair<int,int> right_range = {right, range.second};
if (right_range.first < right_range.second)
new_ranges.push_back(right_range);
}

ranges.swap(new_ranges);
}

private:
vector<pair<int,int>> ranges;
};

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

class RangeModule {
public:
RangeModule() {

}

//O(MlogN) m是erase的区间
void addRange(int left, int right) {
IT l, r;
get_overlap(left, right, l, r);

if (l != r) {
left = min(l->first, left);
right = max(prev(r)->second, right);
ranges.erase(l, r);
}

ranges[left] = right;
}

//O(logN)
bool queryRange(int left, int right) {
IT l, r;
get_overlap(left, right, l, r);

if (l == r)
return false;

return l->first <= left && l->second >= right;
}

//O(MlogN) m是erase的区间
void removeRange(int left, int right) {
IT l, r;
get_overlap(left, right, l, r);

if (l == r) return;

int start = min(left, l->first);
int end = max(right, prev(r)->second);
ranges.erase(l, r);

if (start < left)
ranges[start] = left;
if (end > right)
ranges[right] = end;
}

private:
map<int, int> ranges; //left ==> right

typedef map<int, int>::iterator IT;

void get_overlap(int left, int right, IT &l, IT &r) {
//return [l, r)
l = ranges.upper_bound(left);
r = ranges.upper_bound(right);

if (l != ranges.begin()) {
if (prev(l)->second >= left)
l--;
}
}
};