Интервалы: слияние и вставка

O(n log n)

Отсортируй интервалы по началу, затем пройди один раз: если следующий интервал начинается до конца текущего (или в тот же момент), слей их, расширив конец; иначе закрой текущий интервал и открой новый.

Сигналы

слить перекрывающиеся интервалывставить новый интервал в отсортированный списоквстречи, брони или диапазоны, которые пересекаютсязаданы как пары [начало, конец]свободное/занятое время между интервалами

Шаблон

function mergeIntervals(intervals) {
    intervals.sort((a, b) => a[0] - b[0]);
    const result = [];
    for (const [start, end] of intervals) {
        const last = result[result.length - 1];
        if (last && start <= last[1]) {
            last[1] = Math.max(last[1], end);
        } else {
            result.push([start, end]);
        }
    }
    return result;
}

Похоже, но не то

Линия развёртки (sweep line): Слияние объединяет пересекающиеся диапазоны в меньшее число более широких диапазонов как итоговый ответ. Линия развёртки вместо этого превращает каждый интервал в события +1/-1, чтобы посчитать, сколько активно в какой-то момент, это другой вопрос (пик нагрузки, а не объединённые диапазоны).

n до 1e5 интервалов -> O(n log n): доминирует сортировка; сам проход слияния это один линейный O(n) проход.

Изучить этот паттерн