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

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

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

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

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

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

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

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

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

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

Эти формулировки в условии ведут сюда:

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

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

• Линия развёртки (подсчёт событий) (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).