Слейте все перекрывающиеся интервалы в срезе пар [начало, конец]
Дан срез интервалов [][]int, где каждый элемент — пара [начало, конец]. Верните новый срез, в котором каждая группа перекрывающихся интервалов слита в один. Касающиеся интервалы (когда один заканчивается ровно там, где начинается следующий) считаются перекрывающимися. Цель — O(n log n) по времени.
func merge(intervals [][]int) [][]int {
// ваш код здесь
}Допишите реализацию.
Отсортируйте интервалы по началу, затем пройдите один раз: держите последний интервал в результате; для каждого следующего, если его начало ≤ конца последнего, они перекрываются — расширьте конец последнего до max(lastEnd, end); иначе добавьте его новым интервалом. Результат — минимальный набор непересекающихся интервалов. O(n log n) на сортировку, O(n) на проход.
- ✗Пропустить сортировку, считая, что один проход по несортированному всё сольёт
- ✗Сравнивать только соседние исходные, упуская транзитивную цепочку через бегущий конец
- ✗Брать пересечение вместо объединения при расширении слитого интервала
- →Почему касание (
start == lastEnd) здесь считается перекрытием и когда его можно исключить? - →Как вставить один новый интервал в уже слитый отсортированный список за O(n)?
Задача
Слить все перекрывающиеся интервалы [начало, конец]. Касающиеся считаются перекрывающимися.
func merge(intervals [][]int) [][]int {
if len(intervals) == 0 {
return nil
}
sort.Slice(intervals, func(i, j int) bool {
return intervals[i][0] < intervals[j][0]
})
res := [][]int{intervals[0]}
for _, in := range intervals[1:] {
last := res[len(res)-1]
if in[0] <= last[1] { // перекрытие (касание считается)
if in[1] > last[1] {
last[1] = in[1] // расширяем конец
}
} else {
res = append(res, in)
}
}
return res
}Как это работает
Сортировка по началу делает перекрывающиеся интервалы соседними. Затем один проход держит последний интервал результата:
- если начало текущего
in[0] <= last[1]— они перекрываются, расширяем конец последнего доmax(last[1], in[1]); - иначе текущий не пересекается ни с чем предыдущим — добавляем его как новый.
last — это срез, ссылающийся на элемент res, поэтому last[1] = in[1] правит результат на месте. Сортировка даёт O(n log n), проход — O(n).
