Length of the union of intervals on a line in $O(n\log n)$

Given $n$ segments on a line, each one by a pair of coordinates $(x_{2i}, x_{2i+1})$, find the length of their union.

The following algorithm was proposed by Klee in 1977. It works in $O(n\log n)$ and has been proved to be the asymptotically fastest.

Solution

Store in an array $X$ the endpoints of all the segments sorted by its value, with the left end first if their values are equal, and wether it is a left end or a right end of a segment. Now go through the array keeping a counter $C$ of overlapping segments. If $C$ is non-zero, then add $x_i-x_{i-1}$ to the answer; if the current element is a left end we increase this counter, and otherwise we decrease it.

Implementation

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

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

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