Number of intersections between two ranges | Java implementation of above approach ; Function to return total number of intersections ; Maximum possible number of intersections ; Store all starting points of type1 ranges ; Store all endpoints of type1 ranges ; Starting point of type2 ranges ; Ending point of type2 ranges ; Subtract those ranges which are starting after R ; Subtract those ranges which are ending before L ; Driver Code
import java . io . * ; import java . util . * ; class GFG { static int upperBound ( ArrayList < Integer > a , int low , int high , int element ) { while ( low < high ) { int middle = low + ( high - low ) / 2 ; if ( a . get ( middle ) > element ) { high = middle ; } else { low = middle + 1 ; } } return low ; } static int FindIntersection ( ArrayList < ArrayList < Integer > > type1 , int n , ArrayList < ArrayList < Integer > > type2 , int m ) { int ans = n * m ; ArrayList < Integer > start = new ArrayList < Integer > ( ) ; ArrayList < Integer > end = new ArrayList < Integer > ( ) ; for ( int i = 0 ; i < n ; i ++ ) { start . add ( type1 . get ( i ) . get ( 0 ) ) ; end . add ( type1 . get ( i ) . get ( 1 ) ) ; } Collections . sort ( start ) ; Collections . sort ( end ) ; for ( int i = 0 ; i < m ; i ++ ) { int L = type2 . get ( i ) . get ( 0 ) ; int R = type2 . get ( i ) . get ( 1 ) ; ans -= start . size ( ) - upperBound ( start , 0 , start . size ( ) , R ) ; ans -= upperBound ( end , 0 , end . size ( ) , L - 1 ) ; } return ans ; } public static void main ( String [ ] args ) { ArrayList < ArrayList < Integer > > type1 = new ArrayList < ArrayList < Integer > > ( ) ; type1 . add ( new ArrayList < Integer > ( Arrays . asList ( 1 , 2 ) ) ) ; type1 . add ( new ArrayList < Integer > ( Arrays . asList ( 2 , 3 ) ) ) ; type1 . add ( new ArrayList < Integer > ( Arrays . asList ( 4 , 5 ) ) ) ; type1 . add ( new ArrayList < Integer > ( Arrays . asList ( 6 , 7 ) ) ) ; ArrayList < ArrayList < Integer > > type2 = new ArrayList < ArrayList < Integer > > ( ) ; type2 . add ( new ArrayList < Integer > ( Arrays . asList ( 1 , 5 ) ) ) ; type2 . add ( new ArrayList < Integer > ( Arrays . asList ( 2 , 3 ) ) ) ; type2 . add ( new ArrayList < Integer > ( Arrays . asList ( 4 , 7 ) ) ) ; type2 . add ( new ArrayList < Integer > ( Arrays . asList ( 5 , 7 ) ) ) ; int n = type1 . size ( ) ; int m = type2 . size ( ) ; System . out . println ( FindIntersection ( type1 , n , type2 , m ) ) ; } }