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

Условие

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

/*
Пример 1:
Ввод: segments = [[1,2],[2,3],[3,4],[1,3]]
Вывод: 1
Пояснение: достаточно удалить отрезок [1,3], после чего остальные отрезки не пересекаются.

Пример 2:
Ввод: segments = [[1,2],[1,2],[1,2]]
Вывод: 2
Пояснение: нужно удалить два отрезка [1,2], чтобы оставшийся отрезок не имел конфликтов.

Пример 3:
Ввод: segments = [[1,2],[2,3]]
Вывод: 0
Пояснение: удалять ничего не требуется, отрезки уже не пересекаются.
*/

int minRemovals(vector<vector<int>>& segs) {
    
}

Ответ

Сохраняйте совместимые отрезки в порядке возрастания правой границы. Самый рано заканчивающийся отрезок оставляет максимум места следующим; число удалений равно общему числу минус сохранённые.

int minRemovals(std::vector<std::vector<int>>& segs) {
    if (segs.empty()) return 0;
    std::sort(segs.begin(), segs.end(), [](const auto& a, const auto& b) {
        return a[1] < b[1];
    });
    int removed = 0;
    int end = segs[0][1];
    for (std::size_t i = 1; i < segs.size(); ++i) {
        if (segs[i][0] < end) ++removed;
        else end = segs[i][1];
    }
    return removed;
}

По примерам касание границ не считается пересечением. Предполагаются пары start < end и представимость счётчика в int. Сортировка меняет вход; время O(n log n). При конфликте сохраняем более ранний конец, поэтому не сокращаем доступные варианты продолжения.