algorithm - 在调度程序时间轴上检测冲突(算法)

假设我正在一个24小时日历上绘制一个(StartTime,EndTime)事件，类似于outlook。我的目标是检测重叠（冲突）并将它们分开，使每一列占据窗口宽度的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;
   }

这在大多数情况下都有效，但会引入一个带有结束时间的问题。例如，考虑下图：

最后一个事件应该是4（而不是3）的拆分组的一部分。它没有包含在冲突分割中，因为前一个事件的EndTime与它的StartTime不冲突。
在已排序的startTimes数组中，倒数第二个事件的EndTime (4:30)与倒数第二个事件的StartTime (4:45)不冲突。因此，最终的事件4:45 - 6:00没有被包括在整体分组中我应该得到一个跨越02:30 - 06:00时间区域的4列拆分布局。
我的算法是正确的还是有更好的方法？

最佳答案

问题是“冲突”关系不是可传递的，因此不是等价关系，但您需要一个等价关系，以便将它们放入具有共享水平宽度的等价类中。为了实现这一点，我们必须定义一个新的关系，它是一个等价关系（因此是传递的），然后找出如何计算它。
获得一个等价关系可能和获取“冲突”关系的传递闭包一样简单。也就是说，我们可以“添加”所有缺少的成员以使关系可传递。一种方法是保持代码基本相同，但不要记住最后的开始/结束时间，而是记住第一个（因此是最早的；我们仍然需要排序）开始时间和最后一个停止时间，并使用它来检测“冲突”：

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

关于algorithm - 在调度程序时间轴上检测冲突(算法)，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/46778439/