检测时间线上的冲突，第 2 部分：隔离“真实”重叠

这是我关于绘制重叠时间冲突的时间轴调度算法的原始问题的延续： PART 1: 检测调度程序时间线上的冲突（算法）

我得到了正确的算法，如下所示，在 24 小时时间轴上分割“冲突”事件，使冲突组中的每个项目占据窗口的 N%。

我当前的问题（第 2 部分）是冲突的事件被视为一个组并且总是平等地划分，但是真正的目标是只隔离“真正的冲突”，这些冲突不一定是整个群体.

考虑下图。

这里，原始算法来自Part 1为事件分配了三路

12:30am - 1:30am
1:00am - 2:30am
2:00am - 4:00am

但这个结果有点不正确。只有 2 处重叠，并且应该显示 2 列。事件 #3 可以转移到第 1 列，因为它与事件 #1 不冲突。唯一的冲突（最大 2 路分割）是#1 与#2 冲突，#3 也与#2 冲突。如灰色箭头所示，这种情况下应该有 2 列。

第 1 部分中的原始冲突检测算法：

 * 1) First sort all events by StartTime
 * 2) Initialize "lastMaxEndTime" to EndTime of First Event (#1)
 * 3) LOOP: For each Event: look at Current Event and Next Event (n+1)
 *          If Next Event Exists
 *              if (lastMaxEndTime > NextEvent StartTime) --> CONFLICT!
 *                  - set Overlap mode 
 *                  - push conflicting Current Event's StartTime into conflict array
 *                  - UPDATE: lastMaxEndTime = MAX(lastMaxEndTime, NextEvent EndTime)
 *              else --> NO CONFLICT
 *                  - if we are in Overlap Mode, this is the last overlap
 *                      - push this final conflicting Current Event's StartTime into conflict array
 *                      - draw overlaps now
 *                      - reset Overlap Mode and clear conflict array
 *                  - else
 *                      - this is a normal event, draw at 100%
 *                  - UPDATE: lastMaxEndTime = endTimeNext
 *                  
 *          Else (No Next Event, this is the last event)
 *                  - if we are in Overlap Mode, this is the last overlap
 *                      - push this final conflicting Current Event's StartTime into conflict array
 *                      - draw overlaps now
 *                      - reset Overlap Mode and clear conflict array
 *                  - else
 *                      - this is a normal event, draw at 100%

或者，这个伪代码与帕特里克的答案略有不同，

   // 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
      }
   }

您需要将事件划分为“通道”，即不重叠事件的序列。使用“贪婪”算法这通常很容易。按顺序考虑事件。对于每个事件，将该事件放置在没有重叠的第一个“通道”（图表上的垂直列）中。如果当前事件与所有列重叠，则将其放入新列中。