我想做的是有效地处理间隔。例如,在我的示例中,间隔如下所示:
[10, 20], [15, 25], [40, 100], [5, 14]
区间是封闭的整数,有些区间可能重叠。我想高效 为给定查询找到重叠间隔。例如,如果给出 [16, 22]
:
[10, 20], [15, 25]
上述区间应计算为重叠区间。
我目前正在写一个基于红黑树的区间树(引用:CLRS,Introduction to Algorithms)。虽然找到所有 重叠间隔可以是 O(n),但运行时间应该更快。请注意,可以删除和插入间隔。
不过,我刚刚发现Boost有interval_map
和interval_set
:
http://www.boost.org/doc/libs/1_46_1/libs/icl/doc/html/index.html
我试过了,但这种行为对我来说很奇怪。例如,如果先插入 [2, 7]
,然后插入 [3, 8]
,则生成的 map 将具有 [2, 3)
、[3, 7]
、(7, 8]
。即插入新的区间时,自动进行拆分。
我可以关闭这个功能吗?或者,Boost 的 interval_map
是否适合我的目的?
最佳答案
您需要一种可以有效找到重叠的数据结构。这是通过在数据结构中存储重叠来实现的。现在你似乎在提示它已经这样做了。
这个例子解释了逻辑:
typedef std::set<string> guests;
interval_map<time, guests> party;
party += make_pair(interval<time>::right_open(time("20:00"), time("22:00")),
guests("Mary"));
party += make_pair(interval<time>::right_open(time("21:00"), time("23:00")),
guests("Harry"));
// party now contains
[20:00, 21:00)->{"Mary"}
[21:00, 22:00)->{"Harry","Mary"} //guest sets aggregated on overlap
[22:00, 23:00)->{"Harry"}
当您添加两个重叠区间时,您实际上创建了三个具有不同属性的区间。重叠在两个原始间隔中,使其成为与任一原始间隔在逻辑上不同的间隔。两个原始间隔现在跨越具有不同属性的时间(一些与原始间隔重叠,一些不重叠)。这种拆分使得查找重叠变得高效,因为它们在 map 中是它们自己的间隔。
无论如何,Boost 允许您选择 interval combining style .因此,如果您想强制采用一种难以找到重叠的结构,您可以这样做。
关于c++ - 我可以用 Boost interval_map 做到这一点吗?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/7975108/