php - 查找最大的连续时间段集

Question

我在给定的一天有一系列时间段，其中一些重叠，例如(开始，结束):

(10.00, 10.15) (11.00, 11.30) (11.30, 11.45) (11.45, 12.00) 
(11.45, 12.15) (12.15, 12.45) (13.20, 13.30) (14.15, 14.35) (14.35, 14.40)

我想找到最大的连续时间段集。在上面的示例中，有 3 组连续时间(如下所示)，但由于第一组是第二组的较小“替代”，因此应该忽略它，所以我们只剩下 2 和 3。

1. 11.00 - 11.30, 11.30 - 11.45, 11.45 - 12.00
2. 11.00 - 11.30、11.30 - 11.45、11.45 - 12.15、12.15 - 12.45
3. 14.15 - 14.35, 14.35 - 14.40

有一件事我必须补充:我希望能够指定一个定义连续意味着什么的“公差”。在上面的示例中，连续意味着第一个时间段的结束时间 == 下一个时间段的开始时间，但是将连续定义为“相隔 5 分钟”的时间段会很好。

任何有关如何在 php 或伪代码中执行此操作的想法将不胜感激!

Answer 1

这感觉像是 Dynamic Programming有点问题。我想它也可以作为图形问题来解决。

如果您将数据转换为图形:每个周期都是一个顶点，如果两个顶点是连续的(为此使用您想要的任何容差级别)，则两个顶点相连。所有边具有相同的权重。现在你需要找到 longest path在那个图表上。

最长路径问题是一个 NP 完全问题，这很糟糕。然而，对于没有循环的图，可以在多项式时间内解决这个问题。凉爽的。我希望你的图表是非循环的(你不会整天都在转，对吧？)。因此，只需在每条边上放置一个 -1 的权重，然后找到最短的图。我提供的最后一个链接也有一个动态编程方法。