Length of the union of segments

Given \(n\) segments on a line, each described by a pair of coordinates \((a_{i1}, a_{i2})\). We have to 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 proven to be the asymptotically optimal.

Solution

We store in an array \(x\) the endpoints of all the segments sorted by their values. And additionally we store whether it is a left end or a right end of a segment. Now we iterate over the array, keeping a counter \(c\) of currently opened segments. Whenever the current element is a left end, we increase this counter, and otherwise we decrease it. To compute the answer, we take the length between the last to \(x\) values \(x_i - x_{i-1}\), whenever we come to a new coordinate, and there is currently at least one segment is open.

Implementation

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