Minimum Circles needed to be removed so that all remaining circles are non intersecting | Java 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
import java . util . Arrays ; import java . util . Comparator ; public class MinimumCirclesTobeRemoved { private class Circle implements Comparator < Circle > { int start ; int end ; public int compare ( Circle a , Circle b ) { if ( a . end == b . end ) { return ( a . start - b . start ) ; } return a . end - b . end ; } } public void CountCircles ( int [ ] c , int [ ] r , int n ) { Circle diameter [ ] = new Circle [ n ] ; for ( int i = 0 ; i < n ; i ++ ) { diameter [ i ] = new Circle ( ) ; diameter [ i ] . start = ( c [ i ] - r [ i ] ) ; diameter [ i ] . end = ( c [ i ] + r [ i ] ) ; } Arrays . sort ( diameter , new Circle ( ) ) ; int count = 0 ; int curr = diameter [ 0 ] . end ; for ( int i = 1 ; i < n ; i ++ ) { if ( diameter [ i ] . start > curr ) { curr = diameter [ i ] . end ; } else { count ++ ; } } System . out . println ( count ) ; } public static void main ( String [ ] args ) { MinimumCirclesTobeRemoved a = new MinimumCirclesTobeRemoved ( ) ; int [ ] c = new int [ ] { 1 , 2 , 3 , 4 } ; int [ ] r = new int [ ] { 1 , 1 , 1 , 1 } ; a . CountCircles ( c , r , c . length ) ; } }