Number of intersections between two ranges | C # 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
using System ; using System . Collections . Generic ; class GFG { static int upperBound ( List < int > a , int low , int high , int element ) { while ( low < high ) { int middle = low + ( high - low ) / 2 ; if ( a [ middle ] > element ) { high = middle ; } else { low = middle + 1 ; } } return low ; } static int FindIntersection ( List < List < int > > type1 , int n , List < List < int > > type2 , int m ) { int ans = n * m ; List < int > start = new List < int > ( ) ; List < int > end = new List < int > ( ) ; for ( int i = 0 ; i < n ; i ++ ) { start . Add ( type1 [ i ] [ 0 ] ) ; end . Add ( type1 [ i ] [ 1 ] ) ; } start . Sort ( ) ; end . Sort ( ) ; for ( int i = 0 ; i < m ; i ++ ) { int L = type2 [ i ] [ 0 ] ; int R = type2 [ i ] [ 1 ] ; ans -= start . Count - upperBound ( start , 0 , start . Count , R ) ; ans -= upperBound ( end , 0 , end . Count , L - 1 ) ; } return ans ; } static public void Main ( ) { List < List < int > > type1 = new List < List < int > > ( ) ; type1 . Add ( new List < int > ( ) { 1 , 2 } ) ; type1 . Add ( new List < int > ( ) { 2 , 3 } ) ; type1 . Add ( new List < int > ( ) { 4 , 5 } ) ; type1 . Add ( new List < int > ( ) { 6 , 7 } ) ; List < List < int > > type2 = new List < List < int > > ( ) ; type2 . Add ( new List < int > ( ) { 1 , 5 } ) ; type2 . Add ( new List < int > ( ) { 2 , 3 } ) ; type2 . Add ( new List < int > ( ) { 4 , 7 } ) ; type2 . Add ( new List < int > ( ) { 5 , 7 } ) ; int n = type1 . Count ; int m = type2 . Count ; Console . WriteLine ( FindIntersection ( type1 , n , type2 , m ) ) ; } }