Слияние пересекающихся отрезков

Условие

Дан двумерный массив, где каждый элемент представляет собой отрезок в виде пары чисел [start, end]. Необходимо объединить все отрезки, которые пересекаются или касаются друг друга, и вернуть полученный массив из непересекающихся отрезков.

// Вход:  [][]int{{2,6}, {1,3}, {8,10}, {15,18}}
// Выход: [][]int{{1,6}, {8,10}, {15,18}}

Ответ

Отсортируйте интервалы по началу и объединяйте каждый следующий с последним, если next.start <= last.end. Сложность O(n log n).

Пример с проверкой формы входа и без изменения исходных пар:

import (
    "errors"
    "sort"
)

func MergeIntervals(input [][]int) ([][]int, error) {
    items := make([][2]int, len(input))
    for i, pair := range input {
        if len(pair) != 2 || pair[0] > pair[1] {
            return nil, errors.New("invalid interval")
        }
        items[i] = [2]int{pair[0], pair[1]}
    }
    sort.Slice(items, func(i, j int) bool {
        return items[i][0] < items[j][0]
    })
    result := make([][]int, 0, len(items))
    for _, pair := range items {
        if len(result) == 0 || pair[0] > result[len(result)-1][1] {
            result = append(result, []int{pair[0], pair[1]})
        } else if pair[1] > result[len(result)-1][1] {
            result[len(result)-1][1] = pair[1]
        }
    }
    return result, nil
}

Равенство границ означает касание и тоже объединяется. После сортировки проход линейный, память O(n). Для входа из условия результат [[1,6],[8,10],[15,18]].