text: Check if any K ranges overlap at any point | C ++ implementation of the approach ; Comparator to sort the vector of pairs ; Function that returns true if any k segments overlap at any point ; Starting points are marked by - 1 and ending points by + 1 ; Sort the vector by first element ; Stack to store the overlaps ; Get the current element ; If it is the starting point ; Push it in the stack ; It is the ending point ; Pop an element from stack ; If more than k ranges overlap ; Driver code
code: #include <bits/stdc++.h> NEW_LINE using namespace std ; bool sortby ( const pair < int , int > & a , const pair < int , int > & b ) { if ( a . first != b . first ) return a . first < b . first ; return ( a . second < b . second ) ; } bool kOverlap ( vector < pair < int , int > > pairs , int k ) { vector < pair < int , int > > vec ; for ( int i = 0 ; i < pairs . size ( ) ; i ++ ) { vec . push_back ( { pairs [ i ] . first , -1 } ) ; vec . push_back ( { pairs [ i ] . second , +1 } ) ; } sort ( vec . begin ( ) , vec . end ( ) ) ; stack < pair < int , int > > st ; for ( int i = 0 ; i < vec . size ( ) ; i ++ ) { pair < int , int > cur = vec [ i ] ; if ( cur . second == -1 ) { st . push ( cur ) ; } else { st . pop ( ) ; } if ( st . size ( ) >= k ) { return true ; } } return false ; } int main ( ) { vector < pair < int , int > > pairs ; pairs . push_back ( make_pair ( 1 , 3 ) ) ; pairs . push_back ( make_pair ( 2 , 4 ) ) ; pairs . push_back ( make_pair ( 3 , 5 ) ) ; pairs . push_back ( make_pair ( 7 , 10 ) ) ; int n = pairs . size ( ) , k = 3 ; if ( kOverlap ( pairs , k ) ) cout << " Yes " ; else cout << " No " ; return 0 ; }