Longitud de la unión de segmentos

Dados $n$ segmentos en una recta, cada uno descrito por un par de coordenadas $(a_{i1}, a_{i2})$. Hay que encontrar la longitud de su unión.

El siguiente algoritmo fue propuesto por Klee en 1977. Funciona en $O(n\log n)$ y se ha demostrado que es asintóticamente óptimo.

Solución

Guardamos en un arreglo $x$ los extremos de todos los segmentos ordenados por sus valores. Y además guardamos si es un extremo izquierdo o un extremo derecho de un segmento. Ahora iteramos sobre el arreglo, manteniendo un contador $c$ de segmentos actualmente abiertos. Cuando el elemento actual es un extremo izquierdo, incrementamos este contador, y en caso contrario lo decrementamos. Para calcular la respuesta, tomamos la longitud entre los dos últimos valores de $x$, $x_i - x_{i-1}$, cada vez que llegamos a una coordenada nueva y hay al menos un segmento abierto.

Implementación

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;
}