algorithm - 查找不在树中的间隔

Question

我有一堆可能重叠的(日期)间隔。间隔来自不同的来源。我想“展平”这个“时间轴”，然后找到没有间隔的所有间隔。

如果您查看:http://www.dgp.toronto.edu/people/JamesStewart/378notes/22intervals/到“一个更复杂的例子”部分。因此，我想找到没有 Composer 在世的音程。

我该怎么做？你将如何在 PHP 中实现这样的东西？PHP 是否也有一些简单的构建树的函数？

非常感谢!

编辑我的输入是多个数组(2、3 或 4)，每个数组都包含开始日期和结束日期，如下所示:

 $myarray1[0]['start']['date'] = 'somedate'
 $myarray1[0]['stop']['date'] = 'somedate'
 $myarray1[1]['start']['date'] = 'somedate'
 $myarray1[1]['stop']['date'] = 'somedate'
 $myarray1[2]['start']['date'] = 'somedate'
 $myarray1[2]['stop']['date'] = 'somedate'

同样适用于 myarray2、myarray3 等

Answer 1

基本算法

为每个 Composer 创建两个对象。一个是带有 Composer 姓名和出生年份的出生对象。另一个是死亡对象，同样带有 Composer 的名字和死亡年份。

现在将这些对象排序在一起。

保留一个 int，为 num_composers_alive 初始化为 0。

遍历有序的对象列表。每次遇到出生对象时，递增 num_composers_alive。每次遇到死亡对象时，递减 num_composers_alive。

递增或递减时，每次遇到死亡和递减时，检查 num_composers_alive 是否变为 0。如果是这样，您就进入了一个没有 Composer 活着的时期。输出该数字或将其存储在某处。每次你遇到 birth 和 increment 时，检查 num_composers_alive 现在是否为 1。如果是，你刚刚结束了一个没有 Composer 活着的时期。输出该数字或将其存储在某处。

实现

这将取决于您输入和输出的形式。我不相信 PHP 有树的 native 概念，但我对此可能是错误的。尝试实现上述内容，如果遇到困难，请单独提出一个问题。

老实说，我不确定为什么你需要树来解决上述问题，但也许是为了别的。