我想知道是否有人知道可以有效处理以下情况的数据结构:

数据结构应在某个连续的时间尺度上存储几个可能重叠的可变长度范围。

  • 例如,您可以添加范围a:[0,3], b:[4,7], c:[0,9]
  • 插入时间不需要特别有效。

  • 检索将范围作为参数,并返回集合中与该范围重叠的所有范围,例如:
  • Get(1,2)将返回a和c。 Get(6,7)将返回b和c。 Get(2,6)将返回所有三个。
  • 检索需要尽可能高效。
  • 最佳答案

    您可以使用的一种数据结构是一维R-tree。这些旨在处理范围并提供有效的检索。您还将了解Allen's Operators;时间间隔之间还有许多其他的关系,而不仅仅是“重叠”。

    关于SO的其他问题也会影响到这一领域,包括:

  • Determine Whether Two Date Ranges Overlap
  • Data structure for non-overlapping ranges within a single dimension
  • 09-10 05:19
    查看更多