golang Поиск пересечений списков отрезков времени

У есть два списка отрезков упорядоченных времени "времени" вида:

1) [1, 5] [7, 10]
2) [2, 8] [9, 12] [13, 15]

-- требуется найти список пересечений этих отрезков, напр. в данном случае ответ будет:

[2, 5] [7, 8] [9, 10]

Возможная визуализация:

--------   ---     --------- --------
  ---   ---   ---       ------    -----  -------- -----       ------

Общая идея решения (алгоритм)

Будем действовать так:

• 1) Заведем два "указателя" - который будут смотреть каждый на свой список отрезков
• 2) Будем сравнивать текущие отрезки, пытаться искать пересечение (в смысле очередной отрезок для массива результатов)
• 3) Передвинем тот указатель, правая граница текущего отрезка для которого меньше (тут мы уже достигли сложности $m+n-1$)
• 4) Если мы выходим за пределы хотя бы одного из списков - поиск можно считать оконченным

Релизация в коде

Возможное решение:

package main

import (
	"fmt"
)

// тип для хранения отрезка
type Interval struct {
	start int
	end   int
}

func getIntersenctionList(list1, list2 []Interval) []Interval {
	results := []Interval{}
	i, j := 0, 0
	n, m := len(list1), len(list2)
	for i < n && j < m {
		hasIntersect, result, differense :=
			getIntersectionWithInfo(list1[i], list2[j])
		if hasIntersect {
			results = append(results, result)
		}

		// Решаем как сместить указатели в списках
		if differense > 0 {
			j++
		} else if differense < 0 {
			i++
		} else {
			i++
			j++
		}

	}
	return results
}

func getIntersectionWithInfo(interval1, inteval2 Interval) (hasResult bool, result Interval, difference int) {

	result = Interval{}
	startValue := max(interval1.start, inteval2.start)
	endValue := min(interval1.end, inteval2.end)
	hasResult = startValue < endValue
	if hasResult {
		result = Interval{start: startValue, end: endValue}
	}
	difference = interval1.end - inteval2.end
	return
}

func main() {

	// Пример использования
	list1 := []Interval{
		{start: 1, end: 5},
		{start: 8, end: 10},
		{start: 12, end: 15},
	}

	list2 := []Interval{
		{start: 3, end: 7},
		{start: 9, end: 12},
	}

	fmt.Println(getIntersenctionList(list1, list2))

}

Видео-материалы

• Поиск пересечений отрезков (времени) из двух массивов - Разбор на golang (2026): Ютуб | ВкВидео | Телеграм

Допонительные материалы

• Разбор решения этой же задачи с другой структурой кода на PHP: https://fkn.ktu10.com/?q=node/17496