Klee's Algorithm (Length Of Union Of Segments of a line) - GeeksforGeeks

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;

}

Read full article from Klee's Algorithm (Length Of Union Of Segments of a line) - GeeksforGeeks