Подсчёт общей длины заданных отрезков

Условие

Необходимо реализовать функцию, которая вычисляет суммарную длину всех интервалов, учитывая их возможное перекрытие.

 const intervals = [
    [1, 2],
    [6, 10],
    [7, 9],
    [11, 15]
]

// Ожидаемый результат — 9

Функция должна принимать массив пар чисел, где каждая пара представляет собой границы интервала, и возвращать общую длину объединённого множества отрезков.

Ответ

Отсортируйте интервалы по началу, объедините пересекающиеся и суммируйте длины объединённых участков. Вложенный [7,9] не добавляет длины к [6,10].

function unionLength(intervals) {
  if (!intervals.length) return 0;
  const sorted = [...intervals].sort((a, b) => a[0] - b[0]);
  let [start, end] = sorted[0], total = 0;
  for (let i = 1; i < sorted.length; i++) {
    const [nextStart, nextEnd] = sorted[i];
    if (nextStart <= end) end = Math.max(end, nextEnd);
    else { total += end - start; start = nextStart; end = nextEnd; }
  }
  return total + end - start;
}

Для примера длина 1 + 4 + 4 = 9. Вход предполагает конечные границы start <= end; при недоверенных данных нужна проверка. Исходные пары не изменяются. Время O(n log n), память O(n) для сортируемой копии.