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