Klee 's Algorithm (Length Of Union Of Segments of a line) | C ++ program to implement Klee 's algorithm ; Returns sum of lengths covered by union of given segments ; Initialize empty points container ; Create a vector to store starting and ending points ; Sorting all points by point value ; Initialize result ; To keep track of counts of current open segments ( Starting point is processed , but ending point is not ) ; Traverse through all points ; If there are open points , then we add the difference between previous and current point . ; If this is an ending point , reduce , count of open points . ; Driver program for the above code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int segmentUnionLength ( const vector < pair < int , int > > & seg ) { int n = seg . size ( ) ; 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 ) ; } sort ( points . begin ( ) , points . end ( ) ) ; int result = 0 ; int Counter = 0 ; for ( unsigned i = 0 ; i < n * 2 ; i ++ ) { if ( Counter ) result += ( points [ i ] . first - points [ i - 1 ] . first ) ; ( points [ i ] . second ) ? Counter -- : Counter ++ ; } return result ; } int main ( ) { vector < pair < int , int > > segments ; segments . push_back ( make_pair ( 2 , 5 ) ) ; segments . push_back ( make_pair ( 4 , 8 ) ) ; segments . push_back ( make_pair ( 9 , 12 ) ) ; cout << segmentUnionLength ( segments ) << endl ; return 0 ; }