c++ - C ++排序间隔结构以及删除重叠间隔
问题描述
这里的间隔与 Line 相同。尽管我为这两个目的找到了正确的解决方案:
1) 排序间隔;
2)在添加与现有间隔重叠的间隔时拒绝。
struct Line {
int down;
int up;
Line(int down, int up) {
this->down = down;
this->up = up;
}
};
int main() {
auto cmp = [] (const Line& a, const Line& b) {//NOTE: this can even detect the intersection, as well as sort the interval!!
if (a.up <= b.down) return true;
else return false;
};
set<Line, decltype(cmp)> s(cmp);
Line l1{2, 3};
Line l2{3, 5};
Line l3{1, 2}; //success for insertion
Line l4{4, 6}; //fail for insertion b/c of insersection
auto ret = s.insert(l2);
cout << "insert 3->5 ";
if (ret.second) cout << "success " << endl;
else cout << "fail " << endl;
ret = s.insert(l3);
cout << "insert 1->2 ";
if (ret.second) cout << "success " << endl;
else cout << "fail " << endl;
ret = s.insert(l1);
cout << "insert 2->3 ";
if (ret.second) cout << "success " << endl;
else cout << "fail " << endl;
ret = s.insert(l4);
cout << "insert 4->6 ";
if (ret.second) cout << "success " << endl;
else cout << "fail " << endl;
return 0;
}
Output:
insert 3->5 success
insert 1->2 success
insert 2->3 success
insert 4->6 fail
set finally contains: 1->2, 2->3, 3->5,
有一点让我感到困惑:
1)为什么简单地比较a.up <= b.down
就足以检测重叠间隔?
我们不应该做一些类似检测区间重叠的标准方法吗?
max(a.down, b.down) < min(a.up, b.up)
2)我不清楚第三步
insert 3->5 success
insert 1->2 success //OK, b/c 2 <= 3, a.up <= b.down return true
insert 2->3 success //Why success? 3 > 1, i.e., a.up > b.down, return false; does it only compare with interval 3->5?
3)为什么下面的代码不能用于删除重叠间隔?
auto cmp_set = [](const Line& a, const Line& b) {
if (max(a.down, b.down) < min(a.up, b.up)) return 0; //standard way to detect overlapping of intervals
else { //sort the two intervals
if(a.up <= b.down) return -1;
else return 1;
}
};
解决方案
1)为什么简单地比较 a.up <= b.down 足以检测重叠间隔?
[a.down, a.up[
重叠[b.down, b.up[
时max(a.down, b.down) < min(a.up, b.up)
相当于a.down < b.up && b.down < a.up
(请记住,我们也有a.down <= a.up && b.down <= b.up
区间定义)。
我们还可以列出可能性:
a.down < a.up < b.down < b.up
(a < b)
a.down < b.down < a.up < b.up
路口a.down < b.down < b.up < a.up
十字路口(全包)b.down < a.down < a.up < b.up
十字路口(全包)b.down < a.down < b.up < a.up
路口b.down < b.up < a.down < a.up
(b < a)
第三步我不清楚
insert 3->5 success insert 1->2 success //OK, b/c 2 <= 3, a.up <= b.down return true insert 2->3 success //Why success? 3 > 1, i.e., a.up > b.down, return false; does it only compare with interval 3->5?
Line l1{2, 3};
Line l2{3, 5};
Line l3{1, 2};
Line l4{4, 6};
插入l1
_{l3, l2}
l1 < l2
以前l1
也是l2
!(l1 < l3)
所以l1
不是以前l3
l3 < l1
l1
之后也是如此l3
->{l3, l1, l2}
对于我们有l4
:{l3, l1, l2}
!(l4 < l2)
(l3
与 and类似l1
)所以l4
不是之前l2
!(l2 < l4)
所以l4
不是之后l2
我们两者都有,!(l2 < l4) && !(l4 < l2)
所以有等价的,我们不插入l4
。
3)为什么下面的代码不能用于删除重叠间隔?
我不明白你在哪里使用它。
推荐阅读
- sql-server - 在指定资源组的特定订阅下部署不带 DependsOn 的 ARM 模板
- angular - 在多个动态子域上运行 Angular App
- python - 更新玩家时间mysql
- python - 如何使用 pytest 在 python 中对“request.form”进行单元测试?
- python - Pytest 在多个测试中调用相同的函数导致泄漏
- javascript - 如何在Javascript中的其他div中显示鼠标跟随的圆圈的位置
- python - pie() 缺少 1 个必需的位置参数:'x'
- angular - 我无法从我的计算机访问 Windows Server iis 上的 .net 核心后端
- python - 对于方形 20 节点六边形元素中不同高斯积分点的雅可比行列式,我得到了不同的符号,这是正确的吗?MWE
- javascript - Angualr Datatables:如何使用 javaScript 动态获取所选列值的总和