Klee's Algorithm (Length Of Union Of Segments of a line) - GeeksforGeeks
Given starting and ending positions of segments on a line, the task is to take the union of all given segments and find length covered by these segments.
Read full article from Klee's Algorithm (Length Of Union Of Segments of a line) - GeeksforGeeks
Given starting and ending positions of segments on a line, the task is to take the union of all given segments and find length covered by these segments.
Input : segments[] = {{2, 5}, {4, 8}, {9, 12}}
Output : 9
segment 1 = {2, 5}
segment 2 = {4, 8}
segment 3 = {9, 12}
If we take the union of all the line segments,
we cover distances [2, 8] and [9, 12]. Sum of
these two distances is 9 (6 + 3)
The algorithm was proposed by Klee in 1977. The time complexity of the algorithm is O (N log N). It has been proven that this algorithm is the fastest (asymptotically) and this problem can not be solved with a better complexity.
int segmentUnionLength(const vector <pair <int,int> > &seg){ int n = seg.size(); // Create a vector to store starting and ending // points vector <pair <int, bool> > points(n * 2); for (int i = 0; i < n; i++) { points[i*2] = make_pair(seg[i].first, false); points[i*2 + 1] = make_pair(seg[i].second, true); } // Sorting all points by point value sort(points.begin(), points.end()); int result = 0; // Initialize result // To keep track of counts of current open segments // (Starting point is processed, but ending point // is not) int Counter = 0; // Trvaerse through all points for (unsigned i=0; i<n*2; i++) { // If there are open points, then we add the // difference between previous and current point. // This is interesting as we don't check whether // current point is opening or closing, if (Counter) result += (points[i].first - points[i-1].first); // If this is an ending point, reduce, count of // open points. (points[i].second)? Counter-- : Counter++; } return result;}