Наиболее эффективный способ «закрепить перекрытия» из времени начала и окончания

Question

Предположим, что мы имеем структуру данных:

class Segment{ 
    float startTime; 
    float endTime; 
} 

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

Answer 1

Один из вариантов - создать массив всех начальных и конечных времен, а затем отсортировать его в хронологическом порядке. Затем вы можете перебирать массив слева направо, в каждой точке отслеживая количество открытых интервалов. Всякий раз, когда вы видите время начала, вы увеличиваете количество интервалов, и всякий раз, когда вы видите конечное время, вы уменьшаете количество интервалов. По мере того, как вы это делаете, каждый раз, когда вы переходите от нуля до интервалов, записывайте начало нового интервала, и всякий раз, когда вы переходите от одного открытого интервала к нолю, запишите время закрытия.

В целом, это выполняется во времени O (sort + n). Если вы используете что-то вроде сортировки кучи или быстрого сортировки, это время O (n log n). Если вы используете что-то вроде сортировки radix - считая его применимым - это будет время O (n log U), где U - максимальное значение.

Надеюсь, это поможет!