Algorithme de Klee (longueur de l'union des segments d'une ligne)
Étant donné les positions de début et de fin des segments sur une ligne, la tâche consiste à prendre l'union de tous les segments donnés et à trouver la longueur couverte par ces segments.
Exemples :
Input : segments[] = {{2 5} {4 8} {9 12}} Output : 9 Explanation: 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) Approche:
L'algorithme a été proposé par Klee en 1977. La complexité temporelle de l'algorithme est O (N log N). Il a été prouvé que cet algorithme est le plus rapide (asymptotiquement) et ce problème ne peut être résolu avec une meilleure complexité.
Description :
1) Mettez toutes les coordonnées de tous les segments dans un tableau auxiliaire points[].
2) Triez-le sur la valeur des coordonnées.
3) Une condition supplémentaire pour le tri - s'il y a des coordonnées égales, insérez celle qui est la coordonnée gauche de n'importe quel segment au lieu de celle de droite.
4) Parcourez maintenant l'ensemble du tableau avec le compteur « nombre » de segments qui se chevauchent.
5) Si le décompte est supérieur à zéro alors le résultat est ajouté à la différence entre les points[i] - points[i-1].
6) Si l'élément actuel appartient à l'extrémité gauche, nous augmentons le « nombre », sinon nous le réduisons.
Illustration:
Lets take the example : segment 1 : (25) segment 2 : (48) segment 3 : (912) Counter = result = 0; n = number of segments = 3; for i=0 points[0] = {2 false} points[1] = {5 true} for i=1 points[2] = {4 false} points[3] = {8 true} for i=2 points[4] = {9 false} points[5] = {12 true} Therefore : points = {2 5 4 8 9 12} {f t f t f t} after applying sorting : points = {2 4 5 8 9 12} {f f t t f t} Now for i=0 result = 0; Counter = 1; for i=1 result = 2; Counter = 2; for i=2 result = 3; Counter = 1; for i=3 result = 6; Counter = 0; for i=4 result = 6; Counter = 1; for i=5 result = 9; Counter = 0; Final answer = 9; C++ // C++ program to implement Klee's algorithm #include using namespace std ; // Returns sum of lengths covered by union of given // segments 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 ; // Traverse 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 ; } // Driver program for the above code 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 ; }
Java // Java program to implement Klee's algorithm import java.io.* ; import java.util.* ; class GFG { // to use create a pair of segments static class SegmentPair { int x y ; SegmentPair ( int xx int yy ){ this . x = xx ; this . y = yy ; } } //to create a pair of points static class PointPair { int x ; boolean isEnding ; PointPair ( int xx boolean end ){ this . x = xx ; this . isEnding = end ; } } // creates the comparator for comparing objects of PointPair class static class Comp implements Comparator < PointPair > { // override the compare() method public int compare ( PointPair p1 PointPair p2 ) { if ( p1 . x < p2 . x ) { return - 1 ; } else { if ( p1 . x == p2 . x ){ return 0 ; } else { return 1 ; } } } } public static int segmentUnionLength ( List < SegmentPair > segments ){ int n = segments . size (); // Create a list to store // starting and ending points List < PointPair > points = new ArrayList <> (); for ( int i = 0 ; i < n ; i ++ ){ points . add ( new PointPair ( segments . get ( i ). x false )); points . add ( new PointPair ( segments . get ( i ). y true )); } // Sorting all points by point value Collections . sort ( points new Comp ()); 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 ; // Traverse through all points for ( int i = 0 ; i < 2 * n ; 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 != 0 ) { result += ( points . get ( i ). x - points . get ( i - 1 ). x ); } // If this is an ending point reduce count of // open points. if ( points . get ( i ). isEnding ) { Counter -- ; } else { Counter ++ ; } } return result ; } // Driver Code public static void main ( String [] args ) { List < SegmentPair > segments = new ArrayList <> (); segments . add ( new SegmentPair ( 2 5 )); segments . add ( new SegmentPair ( 4 8 )); segments . add ( new SegmentPair ( 9 12 )); System . out . println ( segmentUnionLength ( segments )); } } // This code is contributed by shruti456rawal
Python3 # Python program for the above approach def segmentUnionLength ( segments ): # Size of given segments list n = len ( segments ) # Initialize empty points container points = [ None ] * ( n * 2 ) # Create a vector to store starting # and ending points for i in range ( n ): points [ i * 2 ] = ( segments [ i ][ 0 ] False ) points [ i * 2 + 1 ] = ( segments [ i ][ 1 ] True ) # Sorting all points by point value points = sorted ( points key = lambda x : x [ 0 ]) # Initialize result as 0 result = 0 # To keep track of counts of current open segments # (Starting point is processed but ending point # is not) Counter = 0 # Traverse through all points for i in range ( 0 n * 2 ): # If there are open points then we add the # difference between previous and current point. if ( i > 0 ) & ( points [ i ][ 0 ] > points [ i - 1 ][ 0 ]) & ( Counter > 0 ): result += ( points [ i ][ 0 ] - points [ i - 1 ][ 0 ]) # If this is an ending point reduce count of # open points. if points [ i ][ 1 ]: Counter -= 1 else : Counter += 1 return result # Driver code if __name__ == '__main__' : segments = [( 2 5 ) ( 4 8 ) ( 9 12 )] print ( segmentUnionLength ( segments ))
C# using System ; using System.Collections ; using System.Collections.Generic ; using System.Linq ; // C# program to implement Klee's algorithm class HelloWorld { class GFG : IComparer < KeyValuePair < int bool >> { public int Compare ( KeyValuePair < int bool > x KeyValuePair < int bool > y ) { // CompareTo() method return x . Key . CompareTo ( y . Key ); } } // Returns sum of lengths covered by union of given // segments public static int segmentUnionLength ( List < KeyValuePair < int int >> seg ) { int n = seg . Count ; // Create a vector to store starting and ending // points List < KeyValuePair < int bool >> points = new List < KeyValuePair < int bool >> (); for ( int i = 0 ; i < 2 * n ; i ++ ){ points . Add ( new KeyValuePair < int bool > ( 0 true )); } for ( int i = 0 ; i < n ; i ++ ) { points [ i * 2 ] = new KeyValuePair < int bool > ( seg [ i ]. Key false ); points [ i * 2 + 1 ] = new KeyValuePair < int bool > ( seg [ i ]. Value true ); } // Sorting all points by point value GFG gg = new GFG (); points . Sort ( gg ); 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 ; // Traverse through all points for ( int 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 != 0 ) result += ( points [ i ]. Key - points [ i - 1 ]. Key ); // If this is an ending point reduce count of // open points. if ( points [ i ]. Value != false ){ Counter -- ; } else { Counter ++ ; } } return result ; } static void Main () { List < KeyValuePair < int int >> segments = new List < KeyValuePair < int int >> (); segments . Add ( new KeyValuePair < int int > ( 2 5 )); segments . Add ( new KeyValuePair < int int > ( 4 8 )); segments . Add ( new KeyValuePair < int int > ( 9 12 )); Console . WriteLine ( segmentUnionLength ( segments )); } } // The code is contributed by Nidhi goel.
JavaScript // JavaScript program to implement Klee's algorithm // Returns sum of lengths covered by union of given // segments function segmentUnionLength ( seg ) { let n = seg . length ; // Create a vector to store starting and ending // points let points = new Array ( 2 * n ); for ( let i = 0 ; i < n ; i ++ ) { points [ i * 2 ] = [ seg [ i ][ 0 ] false ]; points [ i * 2 + 1 ] = [ seg [ i ][ 1 ] true ]; } // Sorting all points by point value points . sort ( function ( a b ){ return a [ 0 ] - b [ 0 ]; }); let result = 0 ; // Initialize result // To keep track of counts of // current open segments // (Starting point is processed // but ending point // is not) let Counter = 0 ; // Traverse through all points for ( let 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 ][ 0 ] - points [ i - 1 ][ 0 ]); // If this is an ending point reduce count of // open points. if ( points [ i ][ 1 ]){ Counter = Counter - 1 ; } else { Counter = Counter + 1 ; } } return result ; } let segments = new Array (); segments . push ([ 2 5 ]); segments . push ([ 4 8 ]); segments . push ([ 9 12 ]); console . log ( segmentUnionLength ( segments )); // The code is contributed by Gautam goel (gautamgoel962)
Sortir
9
Complexité temporelle : O(n * journal n)
Espace auxiliaire : Sur)
