Number of intersections between two ranges | Javascript 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
function upperBound ( a , low , high , element ) { while ( low < high ) { let middle = low + Math . floor ( ( high - low ) / 2 ) ; if ( a [ middle ] > element ) { high = middle ; } else { low = middle + 1 ; } } return low ; } function FindIntersection ( type1 , n , type2 , m ) { let ans = n * m ; let start = [ ] ; let end = [ ] ; for ( let i = 0 ; i < n ; i ++ ) { start . push ( type1 [ i ] [ 0 ] ) ; end . push ( type1 [ i ] [ 1 ] ) ; } start . sort ( function ( a , b ) { return a - b ; } ) ; end . sort ( function ( a , b ) { return a - b ; } ) ; for ( let i = 0 ; i < m ; i ++ ) { let L = type2 [ i ] [ 0 ] ; let R = type2 [ i ] [ 1 ] ; ans -= start . length - upperBound ( start , 0 , start . length , R ) ; ans -= upperBound ( end , 0 , end . length , L - 1 ) ; } return ans ; } let type1 = [ [ 1 , 2 ] , [ 2 , 3 ] , [ 4 , 5 ] , [ 6 , 7 ] ] ; let type2 = [ [ 1 , 5 ] , [ 2 , 3 ] , [ 4 , 7 ] , [ 5 , 7 ] ] ; let n = type1 . length ; let m = type2 . length ; document . write ( FindIntersection ( type1 , n , type2 , m ) ) ;