查找多个间隔之间的重叠
假设我有一个间隔（或范围）列表（例如 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)之间。
基本上，我需要找到项目列表之间的所有重叠部分。
也许我可以使用 3 个独立的区间树来找出答案。 有一个更好的方法吗？
Let's say I have a list of intervals (or ranges) (Eg. 10-15, 5-7, 9-12..). The problem is to find the subset of ranges that overlaps. Of course I can use Interval tree for this.
The actual problem that I have is there are multiple ranges. Best explained by an example:
- 10-15, 5-7, 9-12
- 1-2, 3-6, 14-15
- 3-5, 9-15, 10-15
In the above case, there is an overlap between (1) and (2) at the second range, and between (3) and (1), (2) at third range.
Basically, I need to find all the overlaps between the list of items.
Maybe I can use 3 separate interval trees to find this out. Is there a better way to do this?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
您可以只构建一棵包含所有区间的区间树。 您只需要跟踪间隔属于哪个范围，例如：
您可以将该结构放入间隔树中并检查是否重叠。 当您获得有问题的区间时，您将能够判断每个区间属于哪个范围。
You could build just one interval tree with all intervals in there. You'll just need to keep track of which range the interval belonged to, such as:
You can put that structure inside an interval tree and check for overlapping. When you get the problematic intervals, you'll be able to tell which range each one belonged to.
区间 [a0, b0] 和 [a1, b1] 重叠当且仅当 min(b1,b0) > 最大值(a1,a0)
Intervals [a0, b0] and [a1, b1] overlap iff min(b1,b0) > max(a1,a0)