查找最大的集连续时期

我有时间段的阵列中的某一天，其中一些重叠，像这样（开始，结束）：查找最大的集连续时期

(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

11.00 - 11.30，11.30 - 11.45，11.45 - 12.00
11.00 - 11.30，11.30 - 11.45，11.45 - 12.15，12.15 - 12.45
14.15 - 14.35，14.35 - 14.40

有一件事我必须补充：我希望能够指定一个“容忍”，它定义了什么连续的手段。在上面的例子中，连续的意思是第一个时间段的结束时间==下一个时间段的开始时间，但是将连续的时间段定义为'5分钟分开'会很好。

有关如何在php或伪代码中做到这一点的任何想法将不胜感激！

来源

2012-03-07 ringpull

这些时间总是会在同一天，或者他们可以在不同的顺序和交叉日？ – 2012-03-07 01:00:30

是的，他们都会在同一天。在13.30 - 13.40和13.30 - 13.45等时间段的情况下，我猜'按顺序'是指最小的第一个？无论哪种方式，把他们在某种秩序并不困难:) – ringpull 2012-03-07 01:11:09

这感觉就像一个Dynamic Programming类问题。我想这也可以解决为一个图形问题。

如果您将数据转化为图形：每个周期都是一个顶点，如果两个顶点连续（使用任何所需的容差级别），则连接两个顶点。所有的边都有相同的重量。现在您需要在该图上找到longest path。

最长的路径问题是一个NP完整，这是一个无赖。但是，对于没有周期的图形，可以在多项式时间内解决这个问题。凉。你的图形是一个循环的，我希望（你不会整整一天，对吧？）。因此，只需在每个边上放置-1的权重，并找到最短的图。我提供的最后一个链接也有一个动态编程方法。

来源

2012-03-07 01:02:12 zmbq

这真的很有帮助，谢谢。我已经实现了在您提供的最后一个链接上给出的算法，但是我无法调整它以获取实际路径。它说我必须介绍一个'前辈阵列'，但我不确定它们是什么意思？ – ringpull 2012-03-07 12:48:42

报废 - 想通了！ – ringpull 2012-03-07 16:14:06

这个问题有一个简单的greedy解决方案。首先按开始日期升序排序时间段，如果相等则按结束日期降序排序。现在循环遍历时间段并跟踪当前设置（它位于最左边和最右边的位置）。这里是伪代码（或一些PHP/C++/JS混合） -

bool comp(A, B) { 
    if(A.start == B.start) return A.end > B.end; 
    return A.start < B.start; 
} 

function getLongestSet(periods) { //convert the times to integer first, period is pair of integers 
    sort (periods, comp); 
    longestPeriod = 0; 
    for(i = 0; i < periods.length; i++) { 
     if(periods[i].start > curRight + TOLERANCE) { //start new set 
      curLeft = periods[i].start, curRight = periods[i].end; 
     } 
     else { //expand current set 
      curRight = max(curRight, periods[i].end); 
     } 
     longestPeriod = max(longestPeriod, curRight - curLeft); 
    } 
    return longestPeriod; 
}

来源

2012-03-07 03:47:51

查找最大的集连续时期

回答

相关问题