Обнаружение конфликтов на временной шкале планировщика (алгоритм)

Question

Предположим, я планирую события с (StartTime,EndTime) на 24-часовой календарь похож на 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;    
   }

Это работает большую часть времени, но представляет какую-то проблему с EndTimes. Например, рассмотрите изображение ниже:

Последнее событие должно быть частью Сплит-группы из 4 (не 3). Он не был включен в разделение конфликта, потому что предыдущий EndTime не конфликтует с его StartTime,

В отсортированном массиве StartTimes предпоследнее событие EndTime (4:30) не конфликтует с последним событием StartTime (4:45), Итак, финальное событие 4:45 - 6:00 не были включены в общую группу Split. Я должен был получить раскол с 4 столбцами для охвата области времени 02:30 - 06:00,

Я правильно делаю этот алгоритм или есть лучший способ?

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