Линия развёртки (подсчёт событий)

Линия развёртки (подсчёт событий): как это работает?

Каждый интервал превращается в два события. Начало на левой координате, конец на правой.

Сложите все события в один список. Начало несёт плюс один, конец минус один.

Отсортируйте список по координате. Для совпадений нужно правило, и оно зависит от задачи.

Идите по отсортированным событиям и ведите счётчик. Он всегда хранит число открытых интервалов.

На каждом шаге записывайте то, что просит задача. Обычно это максимум, которого достиг счётчик.

Координатам не нужно быть плотными. Важен только их взаимный порядок.

1. встречи [1, 4], [2, 5], [7, 9]Три встречи превращаются в шесть отдельных событий.
2. 1+, 2+, 4-, 5-, 7+, 9-События отсортированы по времени. Интервалов больше нет.
3. счётчик = 1 в момент 1Открывается первая встреча. Занята одна комната.
4. счётчик = 2 в момент 2Вторая открылась до конца первой. Нужны две комнаты.
5. счётчик = 0 в момент 5Обе закрылись до момента 7. Пик равнялся двум.

function maxOverlap(intervals) {
    const events = [];
    for (const [start, end] of intervals) {
        events.push([start, 1]);
        events.push([end, -1]);
    }
    events.sort((a, b) => a[0] - b[0] || a[1] - b[1]);
    let active = 0;
    let best = 0;
    for (const [, delta] of events) {
        active += delta;
        best = Math.max(best, active);
    }
    return best;
}

Линия развёртки (подсчёт событий): разбор примера

Сколько нужно переговорных комнат

Даны время начала и конца каждой встречи. Найдите наименьшее число комнат, вмещающее все встречи.

Двум встречам нужны разные комнаты, если они пересекаются.

Отсортируйте начала и концы в два отдельных списка.

Идите по ним вместе: начало занимает комнату, конец возвращает. Ответ это пик счётчика.

function minMeetingRooms(intervals) {
    const starts = intervals.map((i) => i[0]).sort((a, b) => a - b);
    const ends = intervals.map((i) => i[1]).sort((a, b) => a - b);

    let rooms = 0;
    let best = 0;
    let e = 0;

    for (const start of starts) {
        // every meeting already finished hands its room back first
        while (ends[e] <= start) {
            rooms--;
            e++;
        }

        rooms++;
        best = Math.max(best, rooms);
    }

    return best;
}

Линия развёртки (подсчёт событий): когда применять?

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

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

Линия развёртки (подсчёт событий): с чем путают?

• Интервалы: слияние и вставка (Intervals: merge & insert): Слияние держит интервалы целыми и соединяет соприкасающиеся. Развёртка про них забывает и считает.
• Массив разностей (Difference array): Это развёртка, где координаты служат индексами массива. Ей нужен узкий плотный диапазон.
• Бинарная куча / очередь с приоритетом (Binary heap / priority queue): Куча держит открытые интервалы и знает, какой кончится раньше. Счётчик знает только сколько их.
• Префиксные суммы (Prefix sums): Префиксные суммы отвечают по фиксированным позициям массива. Развёртка идёт по событиям в порядке сортировки.

Линия развёртки (подсчёт событий): частые ошибки

• Нет правила для событий в одной точке

  Освобождает ли конец в 5 комнату для начала в 5, меняет ответ. Решите и закодируйте это.

• Сортируют интервалы вместо событий

  Развёртке нужны начала и концы вперемешку. Сортировка целых интервалов держит пары склеенными.

• Читают счётчик после прохода

  Ответом обычно служит пик, а не итоговое значение. Итоговое почти всегда ноль.

• Индексируют массив координатой

  Метки времени до 1e9 не бывают индексами массива. Сортируйте события вместо выделения памяти.

Линия развёртки (подсчёт событий): задачи с собеседований

• Переговорные комнаты II: Пик счётчика и есть число комнат.
• Совместные поездки: Пассажиры садятся и выходят на одном маршруте.
• Мой календарь III: Счётчик не должен переходить лимит броней.
• Сколько цветов цветёт: Считайте, сколько диапазонов накрывают каждый спрошенный день.
• Задача о силуэте города: Развёртка с кучей, хранящей текущие высоты.
• Свободное время сотрудников: Все промежутки, где счётчик равен нулю.
• Год максимального населения: Рождения и смерти как события на временной оси.

Линия развёртки (подсчёт событий): сложность по времени и памяти

O(n log n)

n интервалов дают 2n событий, значит O(n log n) на сортировку. Сам проход стоит O(n).