查找最大的集連續時期

我有時間段的陣列中的某一天，其中一些重疊，像這樣（開始，結束）：查找最大的集連續時期

(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

查找最大的集連續時期

回答

相關問題