Klee 's Algorithm (Length Of Union Of Segments of a line) | 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 as 0 ; 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 code
def segmentUnionLength ( segments ) : NEW_LINE INDENT n = len ( segments ) NEW_LINE points = [ None ] * ( n * 2 ) NEW_LINE for i in range ( n ) : NEW_LINE INDENT points [ i * 2 ] = ( segments [ i ] [ 0 ] , False ) NEW_LINE points [ i * 2 + 1 ] = ( segments [ i ] [ 1 ] , True ) NEW_LINE DEDENT points = sorted ( points , key = lambda x : x [ 0 ] ) NEW_LINE result = 0 NEW_LINE Counter = 0 NEW_LINE for i in range ( 0 , n * 2 ) : NEW_LINE INDENT if ( i > 0 ) & ( points [ i ] [ 0 ] > points [ i - 1 ] [ 0 ] ) & ( Counter > 0 ) : NEW_LINE INDENT result += ( points [ i ] [ 0 ] - points [ i - 1 ] [ 0 ] ) NEW_LINE DEDENT if points [ i ] [ 1 ] : NEW_LINE INDENT Counter -= 1 NEW_LINE DEDENT else : NEW_LINE INDENT Counter += 1 NEW_LINE DEDENT DEDENT return result NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT segments = [ ( 2 , 5 ) , ( 4 , 8 ) , ( 9 , 12 ) ] NEW_LINE print ( segmentUnionLength ( segments ) ) NEW_LINE DEDENT