檢測計劃程序時間軸上的衝突（算法）

Question

假設我在類似於Outlook的24小時日曆上繪製(StartTime,EndTime)事件。我的目標是檢測重疊（衝突）並將其拆分，使每列佔用窗口寬度的N％，其中N =該時間幀中的衝突總數。

我的問題是，我的算法

1) first, sort all events by StartTime 
2) LOOP: looks at neighbors: CurrentEvent and NextEvent (n+1): 

    if NextEvent exists { 

     if (CurrentEvent EndTime > NextEvent StartTime) { // CONFLICT! 
     overlappingMode = true; 
     overlappingEvents.add(currentEvent); // Add to array 
     } 
     else { // NO CONFLICT 
     if (overlappingMode is TRUE) { 
      // Resolve Now 
      redrawOverlappingEvents(overlappingEvents); 
      // Reset 
      overlappingMode = false; 
      EMPTY overlappingEvents; 
     } 
     } 
    } 

3) After the loop, also for the last element, 

    if (Overlap Mode is still TRUE) { 
     overlappingEvents.add(currentEvent); // Add to array also 
     // Now Resolve 
     redrawOverlappingEvents(overlappingStartTimes); 
     // Reset 
     overlappingMode = false; 
     EMPTY overlappingEvents;  
    } 

這工作的大部分時間，但引入了某種與EndTimes的問題。例如，考慮下面的圖片：

的最後一個事件應該是4（不是3）裂集團的一部分。它並未包含在衝突分割中，因爲前一個事件的EndTime與其StartTime不衝突。

在StartTimes的Sorted數組中，倒數第二個事件的EndTime (4:30)與上一個事件的StartTime (4:45)不衝突。所以最終的事件4:45 - 6:00沒有包含在整個Split羣組中。我應該得到跨越02:30 - 06:00的時間區域的4列分割佈局。

我正在做這個算法，還是有更好的方法？

Answer 1

問題在於「衝突」關係不是傳遞性的，因此不是等價關係，但是您希望有一個等價關係，因此您可以將它們放到具有共享水平寬度的等價類中。爲此，我們必須定義一個新的關係，它是一個等價關係（因此是可傳遞的），然後找出如何計算它。

獲得一個等價關係可以像獲取「衝突」關係的傳遞閉包一樣簡單。也就是說，我們可以「添加」所有缺失的成員以使關係傳遞。做到這一點的一種方法是保持代碼基本相同，但不要記住最後的開始/結束時間，記住第一個（因此最早;我們仍然需要排序）開始時間和最近的停止時間，並使用該方法檢測 「衝突」：

// first event is the current event 
    lastMaxEndTime = CurrentEvent EndTime 

    if NextEvent exists { 

     // if the maximum end time considered in 
     // the conflicting component currently 
     // under consideration extends beyond the 
     // the next event's start time, then this 
     // and everything that "conflicts" with it 
     // is also defined to "conflict" with NextEvent 
     if (lastMaxEndTime > NextEvent StartTime) { // CONFLICT! 
     overlappingMode = true; 
     overlappingEvents.add(currentEvent); // Add to array 
     lastMaxEndTime = max(lastMaxEndTime, NextEvent EndTime) 
     } 
     else { // NO CONFLICT 
     if (overlappingMode is TRUE) { 
      // Resolve Now 
      redrawOverlappingEvents(overlappingEvents); 
      // Reset 
      overlappingMode = false; 
      EMPTY overlappingEvents; 
     } 

     // everything that starts earlier than me, 
     // ends before I start. so start over 
     lastMaxEndTime = NextEvent EndTime 
     } 
    } 

在你的榜樣，算法做到這一點：

lastMaxEndTime = 2:00 
lastMaxEndTime > 2:30? no, so 
    lastMaxEndTime = 3:30 
lastMaxEndTime > 3:00? yes, so 
    lastMaxEndTime = max(3:30, 5:00) = 5:00 
lastMaxEndTime > 3:15? yes, so 
    lastMaxEndTime = max(5:00, 4:30) = 5:00 <--- this fixed it 
lastMaxEndTime > 4:45? yes, so 
    lastMaxEndTime = max(5:00, 6:00) = 6:00