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

Интервалы: слияние и вставка: как это работает?

Отсортируйте интервалы по значению начала. Без этого порядка дальше ничего не работает.

Возьмите первый интервал как текущий блок. Все следующие сравниваются с ним.

Посмотрите на следующий интервал и его начало. Сравните это начало с текущим концом.

Если начало не позже текущего конца, интервалы соприкасаются. Расширьте конец до большего из двух.

Если начало позже, блок закончен. Запишите его и сделайте новый интервал текущим.

Один проход покрывает весь список. Последний блок записывается после цикла.

1. текущий = [1, 3]Список отсортирован по началу. Первый интервал открывает блок.
2. следующий = [2, 6]2 не позже 3, значит есть пересечение. Конец растёт до 6.
3. текущий = [1, 6], следующий = [8, 10]8 позже 6. Блок закончен и записан.
4. текущий = [8, 10], следующий = [9, 12]9 не позже 10. Конец растёт до 12.
5. [[1, 6], [8, 12]]Последний блок записан после цикла. Четыре интервала стали двумя.

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;
}

function mergeIntervals(intervals: number[][]): number[][] {
    intervals.sort((a, b) => a[0] - b[0]);
    const result: number[][] = [];
    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;
}

def merge_intervals(intervals):
    intervals.sort(key=lambda x: x[0])
    result = []
    for start, end in intervals:
        if result and start <= result[-1][1]:
            result[-1][1] = max(result[-1][1], end)
        else:
            result.append([start, end])
    return result

function mergeIntervals(array $intervals): array {
    usort($intervals, fn($a, $b) => $a[0] <=> $b[0]);
    $result = [];
    foreach ($intervals as [$start, $end]) {
        $lastIdx = count($result) - 1;
        if ($lastIdx >= 0 && $start <= $result[$lastIdx][1]) {
            $result[$lastIdx][1] = max($result[$lastIdx][1], $end);
        } else {
            $result[] = [$start, $end];
        }
    }
    return $result;
}

    public static List<int[]> mergeIntervals(int[][] intervals) {
        Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));
        List<int[]> result = new ArrayList<>();
        for (int[] interval : intervals) {
            int[] last = result.isEmpty() ? null : result.get(result.size() - 1);
            if (last != null && interval[0] <= last[1]) {
                last[1] = Math.max(last[1], interval[1]);
            } else {
                result.add(new int[] { interval[0], interval[1] });
            }
        }
        return result;
    }

    public static List<int[]> MergeIntervals(int[][] intervals) {
        Array.Sort(intervals, (a, b) => a[0].CompareTo(b[0]));
        var result = new List<int[]>();
        foreach (var interval in intervals) {
            var last = result.Count > 0 ? result[^1] : null;
            if (last != null && interval[0] <= last[1]) {
                last[1] = Math.Max(last[1], interval[1]);
            } else {
                result.Add(new int[] { interval[0], interval[1] });
            }
        }
        return result;
    }

Интервалы: слияние и вставка: разбор примера

Вставка интервала в отсортированный список

Дан отсортированный список непересекающихся интервалов и один новый интервал.

Вставьте его, слейте всё, чего он касается, и сохраните порядок без пересечений.

Перенесите все интервалы, которые кончаются до начала нового.

Потом поглотите все пересекающиеся, расширяя новый интервал. Оставшийся хвост перенесите как есть.

function insert(intervals, newInterval) {
    const result = [];
    let [start, end] = newInterval;
    let i = 0;

    while (i < intervals.length && intervals[i][1] < start) {
        result.push(intervals[i]); // ends before the new one begins
        i++;
    }

    while (i < intervals.length && intervals[i][0] <= end) {
        start = Math.min(start, intervals[i][0]);
        end = Math.max(end, intervals[i][1]); // the later interval may end sooner
        i++;
    }
    result.push([start, end]);

    while (i < intervals.length) {
        result.push(intervals[i]);
        i++;
    }

    return result;
}

Интервалы: слияние и вставка: когда применять?

Паттерн «Интервалы: слияние и вставка» нужен, когда в условии есть слова «слить перекрывающиеся интервалы», «вставить новый интервал в отсортированный список» или «встречи, брони или диапазоны, которые пересекаются». Решение на нём обычно укладывается в O(n log n).

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

Слова в условии для всех паттернов собраны в одной таблице: шпаргалка по паттернам алгоритмов.

Интервалы: слияние и вставка: с чем путают?

Паттерн «Интервалы: слияние и вставка» чаще всего путают с этими паттернами: Линия развёртки (подсчёт событий), Жадный алгоритм (обменный аргумент), Сортировка с пользовательским компаратором и Массив разностей.

• Линия развёртки (подсчёт событий) (Sweep line (event counting)): Развёртка разбивает интервал на два события и считает их. Слияние держит интервалы целыми.
• Жадный алгоритм (обменный аргумент) (Greedy (exchange argument)): Убрать поменьше интервалов это жадный выбор по концу. Слияние просто соединяет пересечения.
• Сортировка с пользовательским компаратором (Sort with a custom comparator): Сортировка по началу это подготовка. Эта страница про проход, который идёт следом.
• Массив разностей (Difference array): Он считает глубину перекрытия в каждой точке. Слияние возвращает интервалы, а не числа.

Интервалы: слияние и вставка: частые ошибки

• Пропускают сортировку

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

• Угадывают знак сравнения

  Соприкасаются ли [1, 2] и [2, 3], решает условие задачи. Прочитайте его до выбора оператора.

• Забывают последний блок

  Текущий интервал записывается только после цикла. Без этого в ответе не хватает одного.

• Берут конец у более позднего интервала

  Более поздний интервал может закончиться раньше. Новый конец это максимум из двух.

Интервалы: слияние и вставка: задачи с собеседований

Паттерн «Интервалы: слияние и вставка» решает такие задачи с собеседований: Слияние интервалов, Вставка интервала, Непересекающиеся интервалы, Переговорные комнаты, Пересечение двух списков интервалов, Свободное время сотрудников и Удаление вложенных интервалов.

• Слияние интервалов: Чистая форма: сортировка по началу и один проход.
• Вставка интервала: Список уже отсортирован, сливать нужно только середину.
• Непересекающиеся интервалы: Жадно оставляйте тот, что кончается раньше.
• Переговорные комнаты: Любое пересечение делает ответ отрицательным.
• Пересечение двух списков интервалов: Два отсортированных списка обходятся двумя указателями.
• Свободное время сотрудников: Слейте все занятые блоки и прочитайте промежутки.
• Удаление вложенных интервалов: Сортируйте по началу, а при равенстве длинный вперёд.

Интервалы: слияние и вставка: сложность по времени и памяти

У паттерна «Интервалы: слияние и вставка» целевая сложность O(n log n).

n до 1e6 стоит O(n log n), и всё это сортировка. Проход после неё стоит O(n).