找出多个间隔之间的重叠
找出多个间隔之间的重叠
提问于 2009-03-17 08:08:39
假设我有一个间隔(或范围)的列表(例如。10-15，5-7，9-12.)问题是如何找到重叠范围的子集。当然，我可以使用区间树来完成这个任务。
我实际遇到的问题是有多个范围。最好用一个例子来解释：
- 10-15，5-7，9-12
- 1-2，3-6，14-15
- 3-5，9-15，10-15
在上述情况下，第二范围有(1)和(2)之间的重叠，在第三范围有(3)和(1)、(2)之间的重叠。
基本上，我需要找到项目列表之间的所有重叠。
也许我可以用三个独立的间隔树来找出这个问题。有更好的方法吗？
回答 2
Stack Overflow用户
发布于 2009-03-17 08:28:18
您可以只构建一个包含所有时间间隔的间隔树。您只需跟踪该间隔属于哪个范围，例如：
{
int range;
int intervalFrom;
int intervalTo;
}您可以将该结构放置在间隔树中，并检查是否存在重叠。当您得到有问题的间隔时，您将能够知道每个区间属于哪个范围。
Stack Overflow用户
发布于 2016-04-20 00:08:47
区间a0，b0和a1，b1重叠当且仅当min(b1，b0) > max(a1，a0)
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/653365
复制相关文章
相似问题
腾讯云开发者
