Comprimento da união de segmentos

Dados $n$ segmentos em uma linha, cada um deles descrito por um par de coordenadas $(a_{i1}, a_{i2})$. Temos que encontrar o comprimento da união deles.

O algoritmo a seguir foi proposto por Klee em 1977. Ele funciona em $O(n logn)$ e provou ser o assintoticamente ideal/otimizado.

Solução

Armazenamos em uma array $x$ os pontos finais de todos os segmentos ordenados por seus valores. Além disso, armazenamos se é uma extremidade esquerda ou direita de um segmento. Agora, iteramos sobre a array, mantendo um contador $c$ dos segmentos abertos no momento. Sempre que o elemento atual for um do "lado esquerdo", aumentamos esse contador e, caso contrário, o diminuímos. Para calcular a resposta, tomamos o comprimento entre o último até os $x$ valores $x_i - x_{i-1}$, sempre que chegamos a uma nova coordenada, e atualmente haver pelo menos um segmento aberto.

Implementação

int length_union(const vector<pair<int, int>> &a) {
    int n = a.size();
    vector<pair<int, bool>> x(n*2);
    for (int i = 0; i < n; i++) {
        x[i*2] = {a[i].first, false};
        x[i*2+1] = {a[i].second, true};
    }

    sort(x.begin(), x.end());

    int result = 0;
    int c = 0;
    for (int i = 0; i < n * 2; i++) {
        if (i > 0 && x[i].first > x[i-1].first && c > 0)
            result += x[i].first - x[i-1].first;
        if (x[i].second)
            c--;
        else
            c++;
    }
    return result;
}