715. Range Module
2024-09-04 17:57:06
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 numbersleft <= x < right. 0 < left < right < 10^9in all calls toaddRange, queryRange, removeRange.- The total number of calls to
addRangein a single test case is at most1000. - The total number of calls to
queryRangein a single test case is at most5000. - The total number of calls to
removeRangein a single test case is at most1000.
Approach #1: C++. [Using Vector]
class RangeModule {
public:
RangeModule() {
}
void addRange(int left, int right) {
vector<pair<int, int>> new_ranges;
bool inserted = false;
for (const auto& it : ranges_) {
if (it.first > right && !inserted) {
new_ranges.emplace_back(left, right);
inserted = true;
}
if (it.first > right || it.second < left) {
new_ranges.push_back(it);
} else {
left = min(left, it.first);
right = max(right, it.second);
}
}
if (!inserted) new_ranges.emplace_back(left, right);
ranges_.swap(new_ranges);
}
bool queryRange(int left, int right) {
int l = 0;
int r = ranges_.size() - 1;
while (l <= r) {
int mid = (l + r) / 2;
if (ranges_[mid].first <= left && ranges_[mid].second >= right)
return true;
else if (ranges_[mid].first > right) {
r = mid - 1;
} else {
l = mid + 1;
}
}
return false;
}
void removeRange(int left, int right) {
vector<pair<int, int>> new_ranges;
for (const auto& it : ranges_) {
if (it.second <= left || it.first >= right) {
new_ranges.emplace_back(it);
} else {
if (it.first < left)
new_ranges.emplace_back(it.first, left);
if (it.second > right)
new_ranges.emplace_back(right, it.second);
}
}
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);
*/
there are some notes about STL.
1. the difference between emplace_back and push_back.
3. the method of swap in vector.
Approach #2: C++. [map]
class RangeModule {
public:
RangeModule() {
}
void addRange(int left, int right) {
IT l, r;
getOverLapRanges(left, right, l, r);
if (l != r) {
auto last = r; last--;
left = min(left, l->first);
right = max(right, last->second);
ranges_.erase(l, r);
}
ranges_[left] = right;
}
bool queryRange(int left, int right) {
IT l, r;
getOverLapRanges(left, right, l, r);
if (l == r) return false;
return l->first <= left && l->second >= right;
}
void removeRange(int left, int right) {
IT l, r;
getOverLapRanges(left, right, l, r);
if (l == r) return ;
auto last = r; last--;
int start = min(left, l->first);
int end = max(right, last->second);
ranges_.erase(l, r);
if (start < left) ranges_[start] = left;
if (end > right) ranges_[right] = end;
}
private:
typedef map<int, int>::iterator IT;
map<int, int> ranges_;
void getOverLapRanges(int left, int right, IT& l, IT& r) {
l = ranges_.upper_bound(left);
r = ranges_.upper_bound(right);
// judge the left is the leftmost interval?
if (l != ranges_.begin()) {
if ((--l)->second < left) l++;
}
}
};
/**
* 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);
*/
Notes:
最新文章
- CozyRSS开发记录5-订阅列表栏里的项
- 烂泥：CentOS命令学习之tar打包与解压
- 12款最佳Linux命令行终端工具, 20款优秀的 Linux 终端仿真器
- JavaScript实现在textbox输入时自动去数据库匹配并找出类似值列出，选择后记得将值填入本textbox及下一个textbox
- [OSG]如何用Shader得到物体的世界坐标
- 在IIS里面调试asp.net程序
- JavaScript那些事儿(01): 对象
- orcad10.5启动加速
- vs2010环境下将Win32控制台应用程序，改为Win32项目
- Spring Cloud 自定义ConfigServer
- 如何开发由Create-React-App 引导的应用（三）
- James Munkres Topology: Theorem 16.3
- FileProvider的使用及应用更新时提示：解析包出错、失败等问题
- Control4系统对接arduino
- 基于Metronic的Bootstrap开发框架经验总结（16）-- 使用插件bootstrap-table实现表格记录的查询、分页、排序等处理
- js 数组与字符串的相互转化
- Linux 进程管理 ps、top、pstree命令
- laravel中常用的获取路径的函数
- 使用yarn 安装 Vue-DevTools
- HttpClient调用IdentityServer4获取Token并调用接口