Find a pair of overlapping intervals from a given Set | C ++ program to implement the above approach ; Function to find a pair ( i , j ) such that i - th interval lies within the j - th interval ; Store interval and index of the interval in the form of { { l , r } , index } ; Traverse the array , arr [ ] [ ] ; Stores l - value of the interval ; Stores r - value of the interval ; Push current interval and index into tup ; Sort the vector based on l - value of the intervals ; Stores r - value of current interval ; Stores index of current interval ; Traverse the vector , tup [ ] ; Stores l - value of previous interval ; Stores l - value of current interval ; If Q and R are equal ; Print the index of interval ; Stores r - value of current interval ; If T is less than or equal to curr ; Update curr ; Update currPos ; If such intervals found ; Driver Code ; Given l - value of segments ; Given r - value of segments ; Given size ; Function Call
#include <bits/stdc++.h> NEW_LINE using namespace std ; void findOverlapSegement ( int N , int a [ ] , int b [ ] ) { vector < pair < pair < int , int > , int > > tup ; for ( int i = 0 ; i < N ; i ++ ) { int x , y ; x = a [ i ] ; y = b [ i ] ; tup . push_back ( pair < pair < int , int > , int > ( pair < int , int > ( x , y ) , i ) ) ; } sort ( tup . begin ( ) , tup . end ( ) ) ; int curr = tup [ 0 ] . first . second ; int currPos = tup [ 0 ] . second ; for ( int i = 1 ; i < N ; i ++ ) { int Q = tup [ i - 1 ] . first . first ; int R = tup [ i ] . first . first ; if ( Q == R ) { if ( tup [ i - 1 ] . first . second < tup [ i ] . first . second ) cout << tup [ i - 1 ] . second << ' ▁ ' << tup [ i ] . second ; else cout << tup [ i ] . second << ' ▁ ' << tup [ i - 1 ] . second ; return ; } int T = tup [ i ] . first . second ; if ( T <= curr ) { cout << tup [ i ] . second << ' ▁ ' << currPos ; return ; } else { curr = T ; currPos = tup [ i ] . second ; } } cout << " - 1 ▁ - 1" ; } int main ( ) { int a [ ] = { 1 , 2 , 3 , 2 , 2 } ; int b [ ] = { 5 , 10 , 10 , 2 , 15 } ; int N = sizeof ( a ) / sizeof ( int ) ; findOverlapSegement ( N , a , b ) ; }