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
#include <bits/stdc++.h> NEW_LINE using namespace std ; int FindIntersection ( pair < int , int > type1 [ ] , int n , pair < int , int > type2 [ ] , int m ) { int ans = n * m ; vector < int > start , end ; for ( int i = 0 ; i < n ; i ++ ) { start . push_back ( type1 [ i ] . first ) ; end . push_back ( type1 [ i ] . second ) ; } sort ( start . begin ( ) , start . end ( ) ) ; sort ( end . begin ( ) , end . end ( ) ) ; for ( int i = 0 ; i < m ; i ++ ) { int L = type2 [ i ] . first ; int R = type2 [ i ] . second ; ans -= ( start . end ( ) - upper_bound ( start . begin ( ) , start . end ( ) , R ) ) ; ans -= ( upper_bound ( end . begin ( ) , end . end ( ) , L - 1 ) - end . begin ( ) ) ; } return ans ; } int main ( ) { pair < int , int > type1 [ ] = { { 1 , 2 } , { 2 , 3 } , { 4 , 5 } , { 6 , 7 } } ; pair < int , int > type2 [ ] = { { 1 , 5 } , { 2 , 3 } , { 4 , 7 } , { 5 , 7 } } ; int n = sizeof ( type1 ) / ( sizeof ( type1 [ 0 ] ) ) ; int m = sizeof ( type2 ) / sizeof ( type2 [ 0 ] ) ; cout << FindIntersection ( type1 , n , type2 , m ) ; return 0 ; }