Maximum number of intervals that an interval can intersect | C ++ program for the above approach ; Comparator function to sort in increasing order of second values in each pair ; Function to count maximum number of intervals that an interval can intersect ; Create a hashmap ; Sort by starting position ; Traverse all the intervals ; Initialize um [ v [ i ] ] as 0 ; Store the starting and ending point of the ith interval ; Set low and high ; Store the required number of intervals ; Apply binary search to find the number of intervals completely lying to the right of the ith interval ; Find the mid ; Condition for searching in the first half ; Otherwise search in the second half ; Increment um [ v [ i ] ] by n - ans if ans != - 1 ; Sort by ending position ; Traverse all the intervals ; Store the starting and ending point of the ith interval ; Set low and high ; Store the required number of intervals ; Apply binary search to find the number of intervals completely lying to the left of the ith interval ; Increment um [ v [ i ] ] by ans + 1 if ans != - 1 ; Store the answer ; Traverse the map ; Update the overall answer ; Print the answer ; Driver Code ; Function Call
#include <bits/stdc++.h> NEW_LINE using namespace std ; bool compare ( pair < int , int > f , pair < int , int > s ) { return f . second < s . second ; } struct hash_pair { template < class T1 , class T2 > size_t operator() ( const pair < T1 , T2 > & p ) const { auto hash1 = hash < T1 > { } ( p . first ) ; auto hash2 = hash < T2 > { } ( p . second ) ; return hash1 ^ hash2 ; } } ; void findMaxIntervals ( vector < pair < int , int > > v , int n ) { unordered_map < pair < int , int > , int , hash_pair > um ; sort ( v . begin ( ) , v . end ( ) ) ; for ( int i = 0 ; i < n ; i ++ ) { um [ v [ i ] ] = 0 ; int start = v [ i ] . first ; int end = v [ i ] . second ; int low = i + 1 ; int high = n - 1 ; int ans = -1 ; while ( low <= high ) { int mid = low + ( high - low ) / 2 ; if ( v [ mid ] . first > end ) { ans = mid ; high = mid - 1 ; } else { low = mid + 1 ; } } if ( ans != -1 ) um [ v [ i ] ] = n - ans ; } sort ( v . begin ( ) , v . end ( ) , compare ) ; for ( int i = 0 ; i < n ; i ++ ) { int start = v [ i ] . first ; int end = v [ i ] . second ; int low = 0 ; int high = i - 1 ; int ans = -1 ; while ( low <= high ) { int mid = low + ( high - low ) / 2 ; if ( v [ mid ] . second < start ) { ans = mid ; low = mid + 1 ; } else { high = mid - 1 ; } } if ( ans != -1 ) um [ v [ i ] ] += ( ans + 1 ) ; } int res = 0 ; for ( auto it = um . begin ( ) ; it != um . end ( ) ; it ++ ) { res = max ( res , n - it -> second ) ; } cout << res ; } int main ( ) { vector < pair < int , int > > arr = { { 1 , 2 } , { 3 , 4 } , { 2 , 5 } } ; int N = arr . size ( ) ; findMaxIntervals ( arr , N ) ; return 0 ; }