Minimum Circles needed to be removed so that all remaining circles are non intersecting | C ++ implementation of the above approach ; Comparison function modified according to the end value ; Function to return the count of non intersecting circles ; structure with start and end of diameter of circles ; sorting with smallest finish time first ; count stores number of circles to be removed ; cur stores ending of first circle ; non intersecting circles ; intersecting circles ; Driver Code ; centers of circles ; radius of circles ; number of circles
#include <algorithm> NEW_LINE #include <iostream> NEW_LINE using namespace std ; struct circle { int start , end ; } ; bool comp ( circle a , circle b ) { if ( a . end == b . end ) return a . start < b . start ; return a . end < b . end ; } void CountCircles ( int c [ ] , int r [ ] , int n ) { circle diameter [ n ] ; for ( int i = 0 ; i < n ; ++ i ) { diameter [ i ] . start = c [ i ] - r [ i ] ; diameter [ i ] . end = c [ i ] + r [ i ] ; } sort ( diameter , diameter + n , comp ) ; int count = 0 ; int cur = diameter [ 0 ] . end ; for ( int i = 1 ; i < n ; ++ i ) { if ( diameter [ i ] . start > cur ) { cur = diameter [ i ] . end ; } else count ++ ; } cout << count << " STRNEWLINE " ; } int main ( ) { int c [ ] = { 1 , 2 , 3 , 4 } ; int r [ ] = { 1 , 1 , 1 , 1 } ; int n = sizeof ( c ) / sizeof ( int ) ; CountCircles ( c , r , n ) ; return 0 ; }