2

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

如果您查看：http ://www.dgp.toronto.edu/people/JamesStewart/378notes/22intervals/ 到“更复杂的示例”部分。因此，我想找到没有作曲家在世的区间。

我怎么做？你将如何在 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 等也是如此

4

2 回答 2

3

基本算法

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

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

保持一个int, 初始化为0for num_composers_alive。

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

在递增或递减时，每次遇到死亡和递减时，检查是否num_composers_alive为 0。如果是，则您只是进入了一个没有作曲家活着的时期。输出该数字或将其存储在某处。每次点击出生和增量时，检查num_composers_alive现在是否为 1。如果是，则您刚刚结束了一个没有作曲家在世的时期。输出该数字或将其存储在某处。

执行

这将取决于您的输入和输出的形式。我不相信 PHP 有树的原生概念，但我可能错了。尝试实施上述方法，如果遇到困难，请打开一个单独的问题。

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

于 2012-09-12T13:57:49.323 回答
1

一个简单的算法步骤

  1. Define a function that translates a date object to an integer (and vice versa). This is a place where you may need to optimize the translation to make all numbers as small as possible. A date from past must have smaller number then a date from future

  2. Initialize array of numbers. Set all bits to 0. Make sure the size of the array matches the largest date number (from step 1).

  3. Iterate over the date ranges

  4. Mark date range in the array with 1s. Use date translated into a number (step 1) as an index in the array.

  5. Translate all indexes with 0s back to the date intervals.

Runtime complexity O(N). Space complexity O(N).

于 2012-09-12T17:17:22.603 回答