Дан набор отрезков времени [Start, End] (границы включительно, Start <= End) в
произвольном порядке. Объедините все пересекающиеся отрезки и верните результат,
отсортированный по Start. Отрезки, которые касаются концами, тоже пересекаются:
[1, 3] и [3, 5] дают [1, 5]. А [1, 2] и [3, 4] не пересекаются — между ними
есть промежуток.
type Interval struct {
Start, End int
}
// MergeIntervals объединяет пересекающиеся отрезки.
func MergeIntervals(intervals []Interval) []Interval
Примеры
MergeIntervals([]Interval{{11, 13}, {12, 14}, {15, 16}}) // [{11 14} {15 16}]
MergeIntervals([]Interval{{1, 3}, {8, 10}, {2, 6}, {15, 18}}) // [{1 6} {8 10} {15 18}]
MergeIntervals([]Interval{{1, 4}, {4, 5}}) // [{1 5}]
MergeIntervals([]Interval{{1, 10}, {2, 3}}) // [{1 10}]
MergeIntervals(nil) // []
Ограничения: 0 <= len(intervals) <= 10^5, границы — любые int (в том числе
отрицательные). Время O(n log n). Порядок элементов входного слайса функция может
менять.
Устно: что меняется, если интервалы приходят потоком и нужно поддерживать
объединение после каждой вставки?