这里的intervals和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) Why is simply comparing a.up <= b.down enough to detect overlapping intervals?
[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)
The 3rd step is not clear to me
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
和l1
)所以l4
不在l2
之前 -
!(l2 < l4)
所以l4
不在l2
之后
我们都有 !(l2 < l4) && !(l4 < l2)
所以有等效,我们不插入l4
.
3) Why does below code not work for removing overlapping intervals?
我不明白你在哪里使用它。
关于C++ 排序间隔结构以及删除重叠间隔,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/56260963/