Вложенные отрезки

Отрезок называется вложенным, если существует другой отрезок, целиком его содержащий. Задача — оставить только невложенные.

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

Решение

Отсортируем отрезки по левому концу. Тогда отрезок вложен ровно тогда, когда среди уже рассмотренных есть отрезок с правым концом не меньше.

Значит, достаточно вести максимум правых концов:

sort(idx.begin(), idx.end(), [&](int a, int b) {
    if (seg[a].first != seg[b].first) return seg[a].first < seg[b].first;
    return seg[a].second > seg[b].second;      // при равном левом — длинный раньше
});

vector<int> keep;
long long rmax = LLONG_MIN;
for (int i : idx) {
    if (seg[i].second <= rmax) continue;       // вложен
    rmax = seg[i].second;
    keep.push_back(i);
}

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

Сложность — $O(n \log n)$, вся стоимость в сортировке.

Компаратор

Вторая строка компаратора — не мелочь.

При равных левых концах короткий отрезок вложен в длинный. Если короткий пойдёт первым, rmax обновится по нему, и длинный тоже покажется невложенным — а он как раз и есть тот, кто вкладывает.

Поэтому при равном левом конце длинный должен идти раньше: правый конец по убыванию.

Классическая запись через tie тут не годится напрямую — направления сортировки разные. Пишут либо явный if, либо

return tie(seg[a].first, seg[b].second) < tie(seg[b].first, seg[a].second);

Заметьте перестановку a и b во втором поле: это и переворачивает порядок. Приём аккуратный, но неочевидный при чтении — явный if честнее.

Полностью совпадающие отрезки

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

Приведённый код оставит первый из них по порядку сортировки — потому что сравнение <= rmax для первого ещё ложно. Обычно это то, что нужно.

Но перечитайте условие: иногда просят оставить оба, иногда — ни одного. Разница в одном знаке сравнения, а тест на это в наборе почти наверняка есть.

Через события

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

Формулировка длиннее, а результат тот же. Здесь сортировка по левому концу проще — и это нормально: события не обязаны быть лучшим инструментом для каждой задачи про отрезки.

Событийная запись выигрывает, когда вложенность нужна не сама по себе, а вместе с чем-то ещё в том же проходе.

Что даёт результат

После удаления вложенных отрезки упорядочены так, что $l_1 < l_2 < \dots$ и одновременно $r_1 < r_2 < \dots$. Это сильное свойство.

Из него следует:

• отрезки, покрывающие данную точку, образуют непрерывный участок в этом порядке — их можно найти двумя бинарными поисками;
• задача «выбрать максимум непересекающихся» упрощается: жадность по правому концу работает на подряд идущих;
• задача о покрытии отрезка сводится к проходу двумя указателями без всякой кучи.

Поэтому удаление вложенных — стандартный первый шаг во многих задачах про отрезки, даже если в условии про него ни слова.