Объединение отрезков

Даны отрезки, возможно пересекающиеся и вложенные. Нужно найти их объединение: сколько получилось связных кусков, каковы они и какова суммарная длина.

Через баланс

Кусок объединения начинается, когда баланс становится равен единице (был ноль), и заканчивается, когда баланс возвращается к нулю.

long long total = 0, begin_ = 0;
int balance = 0;
for (const Event& e : events) {
    if (e.type == -1) {                    // открытие
        if (balance == 0) begin_ = e.x;
        balance++;
    } else {                               // закрытие
        balance--;
        if (balance == 0) total += e.x - begin_;
    }
}

Обнулять begin_ после закрытия не нужно: следующее открытие с нулевым балансом перезапишет его.

Проверено: на тридцати тысячах случайных наборов длина объединения совпала с прямым подсчётом покрытых единичных клеток.

Сложность — $O(n \log n)$.

Чтобы получить сами куски, а не только длину, добавьте result.push_back({begin_, e.x}) рядом с прибавлением к сумме. Число кусков — размер этого вектора.

Порядок событий здесь

Если требуется, чтобы касающиеся отрезки $[1,3]$ и $[3,5]$ склеились в один кусок $[1,5]$, открытие должно идти раньше закрытия. Тогда в точке 3 баланс не упадёт до нуля.

Если они должны считаться разными кусками (полуинтервалы), порядок обратный.

Для длины объединения это различие ничего не меняет: касание имеет нулевую длину. А вот для числа кусков — меняет, и это надо проверить по условию.

Второй способ: сортировка по левому концу

Ту же задачу решает сортировка по левому концу со слиянием на лету:

sort(seg.begin(), seg.end());
vector<pair<long long, long long>> merged;
for (auto& [l, r] : seg)
    if (!merged.empty() && l <= merged.back().second)
        merged.back().second = max(merged.back().second, r);
    else
        merged.push_back({l, r});

Короче и понятнее. Когда что брать:

	сортировка по левому концу	события
длина и куски объединения	проще	сложнее
нужен ещё и максимум покрытия	не умеет	умеет
нужны запросы в точках	не умеет	умеет
несколько типов объектов сразу	неудобно	естественно

Правило: если нужно только объединение — сортировка по левому концу; если по дороге нужно что-то ещё — события.

max в первой ветке обязателен в обоих подходах: очередной отрезок может целиком лежать внутри предыдущего.

Дополнение к объединению

Иногда просят не покрытые участки, а непокрытые — «дыры». Они получаются из того же прохода: дыра начинается там, где баланс упал до нуля, и кончается там, где снова стал единицей.

Отдельно решается вопрос о краях: считается ли непокрытым всё левее первого отрезка. Обычно нет, но условие стоит перечитать.

Разность и пересечение

Пересечение всех отрезков — задача-минутка: это $[\max l_i,\; \min r_i]$, и если левая граница оказалась правее правой, пересечение пусто.

long long left = LLONG_MIN, right = LLONG_MAX;
for (auto& [l, r] : seg) { left = max(left, l); right = min(right, r); }
bool empty = left > right;

Никаких событий не нужно, один проход.

Разность — вычесть из одного набора отрезков другой — решается событиями с двумя счётчиками: баланс по первому набору и баланс по второму. Участок входит в ответ, когда первый положителен, а второй равен нулю.

Это общий приём: несколько независимых балансов в одном проходе. Так же считается «покрыто ровно одним из двух наборов» и подобные условия.