algorithm - 确定给定日期范围之间是否存在时间重叠

Question

有非常多的数据范围（开始和结束日期）。我试图找到最有效的方法来确定给定的（新）数据范围是否与其他数据范围有任何重叠。有任何想法吗？

标签： algorithm

Answer 1

这是一个恒定时间的方法。在树中维护时间戳：年 -> 月 -> 日 -> 小时 -> 分钟 -> 秒 -> 无论您想要多么细粒度。

要检查新的日期范围：

1. Traverse the tree, creating new nodes as needed, to add the start-of-range 
   timestamp.
2. Back up to the highest common node and retraverse the tree from there, again 
   creating new nodes as needed to add the end-of-range timestamp.
3. As you move between the two timestamps, check every node you pass for children 
   that live between the two timestamps. If you find any then there is overlap.

通过在树中存储更多信息，您可以识别特定的重叠范围（而不是仅存在），并生成重叠范围的数量。

简单的 M/D 示例：

范围 1：1/19 - 3/19

范围 2：2/19 - 4/19

添加范围一后，树具有三个节点：2019 年、1 月和 3 月，边为 2019 -> 1 和 2019 -> 3。

我们通过添加 2019 -> 2 来处理范围 2，然后返回到 2019 并注意到 2019 的子节点 3 位于 2 和 4 之间。最后我们添加第 4 个月的节点。