Алгоритмы/Структуры данных для свертывания перекрывающихся событий на временной шкале

Question

Я ищу алгоритм для выполнения следующего. У меня есть график событий, которые охватывают периоды времени, которые могут перекрываться. Я хотел бы свернуть эти события в единую временную шкалу, не перекрывающую периоды времени, каждый из которых определяется наличием одного или нескольких событий.

Хотя концептуально простой, он может быть немного грязным, чтобы поймать все возможные случаи и соответствующим образом разделить график.

В качестве иллюстрации (здесь горизонтальная ось времени):

Event A ----- 
Event B  ---- 

становится

Event A --- 
Event A+B -- 
Event B  -- 

Другой пример:

A ----------- 
B  --- 
C   -- 

Становится:

A --- 
A+B  --- 
A   -- 
A+C   -- 
A    - 

Существуют ли для этого стандартные алгоритмы/структуры данных?

Answer 1

Укажите время начала и конца каждого события в массиве и отсортируйте их в неубывающем порядке времени (если произойдет «начало» и «конец» и одно и то же время, сломайте связи, конец ").

Мы сделаем алгоритм sweep line.

Пройдите отсортированный массив при сохранении набора «активных» событий: каждый раз, когда вы видите время начала/окончания, соответственно добавляете или удаляете соответствующее событие из набора и добавляете (если активный набор не пуст) событие для вашего решения.

Результирующий набор событий не пересекается и может быть помечен как необходимо.