Find a pair of overlapping intervals from a given Set | 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 ; Given l - value of segments ; Given r - value of segments ; Given size ; Function Call
def findOverlapSegement ( N , a , b ) : NEW_LINE INDENT tup = [ ] NEW_LINE for i in range ( N ) : NEW_LINE INDENT x = a [ i ] NEW_LINE y = b [ i ] NEW_LINE tup . append ( ( ( x , y ) , i ) ) NEW_LINE DEDENT tup . sort ( ) NEW_LINE curr = tup [ 0 ] [ 0 ] [ 1 ] NEW_LINE currPos = tup [ 0 ] [ 1 ] NEW_LINE for i in range ( 1 , N ) : NEW_LINE INDENT Q = tup [ i - 1 ] [ 0 ] [ 0 ] NEW_LINE R = tup [ i ] [ 0 ] [ 0 ] NEW_LINE if Q == R : NEW_LINE INDENT if tup [ i - 1 ] [ 0 ] [ 1 ] < tup [ i ] [ 0 ] [ 1 ] : NEW_LINE INDENT print ( tup [ i - 1 ] [ 1 ] , tup [ i ] [ 1 ] ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( tup [ i ] [ 1 ] , tup [ i - 1 ] [ 1 ] ) NEW_LINE DEDENT return NEW_LINE DEDENT T = tup [ i ] [ 0 ] [ 1 ] NEW_LINE if ( T <= curr ) : NEW_LINE INDENT print ( tup [ i ] [ 1 ] , currPos ) NEW_LINE return NEW_LINE DEDENT else : NEW_LINE INDENT curr = T NEW_LINE currPos = tup [ i ] [ 1 ] NEW_LINE DEDENT DEDENT print ( " - 1" , " - 1" , end = " " ) NEW_LINE DEDENT a = [ 1 , 2 , 3 , 2 , 2 ] NEW_LINE b = [ 5 , 10 , 10 , 2 , 15 ] NEW_LINE N = len ( a ) NEW_LINE findOverlapSegement ( N , a , b ) NEW_LINE