C++ map 212ms

• I use a map to record the interval
for add and remove range, I find all overlapped interval and erase them, then add one or two updated interval

``````class RangeModule {
public:
map<int,int> _map;
RangeModule() {

}

void addRange(int left, int right) {
//cout << "add range " << left << " " << right << endl;
unordered_set<int>to_del;
auto it = _map.lower_bound(left);
if(it != _map.begin()) it--;
while(it != _map.end())
{
if(it -> second < left)
{
it++;
continue;
}
if(it -> first > right) break;
to_del.insert(it -> first);
left = min(left, it -> first);
right = max(right, it -> second);
it++;
}

for(auto e : to_del) _map.erase(e);
_map[left] = right;
}

bool queryRange(int left, int right) {
//printMap();
auto it = _map.lower_bound(left);
if(it != _map.begin()) it--;
while(it != _map.end())
{
if(it -> second < left)
{
it++;
continue;
}
if(it -> first > right) return false;
return it -> first <= left && it -> second >= right;
}
return false;
}

void removeRange(int left, int right) {
//cout << "remove range " << left << " " << right << endl;
unordered_set<int>to_del;
auto it = _map.lower_bound(left);
if(it != _map.begin()) it--;
int v1 = -1, v2 = -1;
while(it != _map.end())
{
if(it -> second <= left)
{
it++;
continue;
}
if(it -> first >= right) break;
if(it -> first < left)
v1 = it -> first;
else
to_del.insert(it->first);
if(it -> second > right) v2 = it -> second;
it++;
}
for(auto e : to_del) _map.erase(e);
if(v1 > 0) _map[v1] = left;
if(v2 > 0) _map[right] = v2;
}

void printMap()
{
cout << "------ print map ------" << endl;
for(auto e : _map) cout << e.first << " " << e.second << endl;
}
};

/**
* 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);
*/``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.