56. Merge Intervals

Задача

Дан массив интервалов intervals , где intervals[i] = [start_i, end_i] , объедините все перекрывающиеся интервалы и верните массив непересекающихся интервалов, которые покрывают все интервалы во входных данных.

Примеры

Пример 1

Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]

Пояснение

Интервалы [1,3] и [2,6] пересекаются — объединяем их в [1,6].

Пример 2

Input: intervals = [[1,4],[4,5]]
Output: [[1,5]]

Пояснение

Интервалы [1,4] и [4,5] считаются пересекающимися.

Пример 3

Input: intervals = [[4,7],[1,4]]
Output: [[1,7]]

Пояснение

Интервалы [1,4] и [4,7] считаются пересекающимися.

Решение

Решение

// Временная: O(n log(n)) — доминирует сортировка. Сам проход по циклу занимает всего O(n)
// Пространственная: O(n) — нужно выделить память под массив result, который в худшем случае (если пересечений нет) будет содержать все элементы.
 
function intervalsMerge(intervals) {
    if (intervals.length <= 1) return intervals;
 
    // O(n log(n))
    intervals.sort((a, b) => a[0] - b[0]);
 
    const result = [];
    let current = intervals[0];
 
    // O(n). Проходим по массиву один раз
    for (let i = 1; i < intervals.length; i++) {
        if (current[1] >= intervals[i][0]) {
            // Интервалы пересекаются - объединяем
            current[1] = Math.max(current[1], intervals[i][1]);
        } else {
            // Интервалы не пересекаются - сохраняем текущий и начинаем новый
            result.push(current);
            current = intervals[i];
        }
    }
 
    // Не забываем добавить последний интервал
    result.push(current);
 
    return result;
}

Решение 2: Функциональный подход (chaining)

// Временная: O(n log(n)) — доминирует сортировка. Сам проход по циклу занимает всего O(n)
// Пространственная: O(n) — нужно выделить память под массив result, который в худшем случае (если пересечений нет) будет содержать все элементы.
 
function intervalsMerge(intervals) {
    if (intervals.length <= 1) return intervals;
 
    return intervals
        // O(n log(n))
        .sort((a, b) => a[0] - b[0])
        // O(n)
        .reduce((acc, interval) => {
            const last = acc[acc.length - 1];
 
            if (!last || last[1] < interval[0]) {
                acc.push(interval);
            } else {
                last[1] = Math.max(last[1], interval[1]);
            }
 
            return acc;
        }, []);
}