Klee 알고리즘(선분의 합집합 길이)
선에서 세그먼트의 시작 및 끝 위치가 주어지면 작업은 주어진 모든 세그먼트의 합집합을 취하고 이러한 세그먼트가 포함하는 길이를 찾는 것입니다.
예:
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) 접근하다:
이 알고리즘은 1977년 Klee에 의해 제안되었습니다. 알고리즘의 시간 복잡도는 O(N log N)입니다. 이 알고리즘은 (점근적으로) 가장 빠르며 이 문제는 더 나은 복잡성으로 해결할 수 없다는 것이 입증되었습니다.
설명 :
1) 모든 세그먼트의 모든 좌표를 보조 배열 points[]에 넣습니다.
2) 좌표값을 기준으로 정렬합니다.
3) 정렬을 위한 추가 조건 - 동일한 좌표가 있는 경우 오른쪽 세그먼트 대신 왼쪽 좌표인 좌표를 삽입합니다.
4) 이제 겹치는 세그먼트의 카운터 '수'를 사용하여 전체 배열을 살펴봅니다.
5) 개수가 0보다 크면 결과는 포인트[i] - 포인트[i-1] 간의 차이에 추가됩니다.
6) 현재 요소가 왼쪽 끝에 속하면 'count'를 늘리고 그렇지 않으면 줄입니다.
삽화:
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)
산출
9
시간 복잡도: O(n * 로그 n)
보조 공간: 에)
