# 715. 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`.

``````class RangeModule {
public:
RangeModule() {}

void addRange(int left, int right) {
vector<pair<int, int>> res;
int n = v.size(), cur = 0;
for (int i = 0; i < n; ++i) {
if (v[i].second < left) {
res.push_back(v[i]);
++cur;
} else if (v[i].first > right) {
res.push_back(v[i]);
} else {
left = min(left, v[i].first);
right = max(right, v[i].second);
}
}
res.insert(res.begin() + cur, {left, right});
v = res;
}

bool queryRange(int left, int right) {
for (auto a : v) {
if (a.first <= left && a.second >= right) return true;
}
return false;
}

void removeRange(int left, int right) {
vector<pair<int, int>> res, t;
int n = v.size(), cur = 0;
for (int i = 0; i < n; ++i) {
if (v[i].second <= left) {
res.push_back(v[i]);
++cur;
} else if (v[i].first >= right) {
res.push_back(v[i]);
} else {
if (v[i].first < left) {
t.push_back({v[i].first, left});
}
if (v[i].second > right) {
t.push_back({right, v[i].second});
}
}
}
res.insert(res.begin() + cur, t.begin(), t.end());
v = res;
}

private:
vector<pair<int, int>> v;
};
``````

``````class RangeModule {
public:
RangeModule() {}

void addRange(int left, int right) {
auto x = find(left, right);
m[x.first] = x.second;
}

bool queryRange(int left, int right) {
auto it = m.upper_bound(left);
return it != m.begin() && (--it)->second >= right;
}

void removeRange(int left, int right) {
auto x = find(left, right);
if (left > x.first) m[x.first] = left;
if (x.second > right) m[right] = x.second;
}

private:
map<int, int> m;

pair<int, int> find(int left, int right) {
auto l = m.upper_bound(left), r = m.upper_bound(right);
if (l != m.begin() && (--l)->second < left) ++l;
if (l == r) return {left, right};
int i = min(left, l->first), j = max(right, (--r)->second);
m.erase(l, ++r);
return {i, j};
}
};
``````

Data Stream as Disjoint Intervals

Insert Interval

Merge Intervals

https://leetcode.com/problems/range-module/discuss/108914/c++-code

https://leetcode.com/problems/range-module/discuss/108912/C++-vector-O(n)-and-map-O(logn)-compare-two-solutions

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation