Find a pair of overlapping intervals from a given Set | Java 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
import java . util . * ; import java . lang . * ; class pair { int l , r , index ; pair ( int l , int r , int index ) { this . l = l ; this . r = r ; this . index = index ; } } class GFG { static void findOverlapSegement ( int N , int [ ] a , int [ ] b ) { ArrayList < pair > tup = new ArrayList < > ( ) ; for ( int i = 0 ; i < N ; i ++ ) { int x , y ; x = a [ i ] ; y = b [ i ] ; tup . add ( new pair ( x , y , i ) ) ; } Collections . sort ( tup , ( aa , bb ) -> ( aa . l != bb . l ) ? aa . l - bb . l : aa . r - bb . r ) ; int curr = tup . get ( 0 ) . r ; int currPos = tup . get ( 0 ) . index ; for ( int i = 1 ; i < N ; i ++ ) { int Q = tup . get ( i - 1 ) . l ; int R = tup . get ( i ) . l ; if ( Q == R ) { if ( tup . get ( i - 1 ) . r < tup . get ( i ) . r ) System . out . print ( tup . get ( i - 1 ) . index + " ▁ " + tup . get ( i ) . index ) ; else System . out . print ( tup . get ( i ) . index + " ▁ " + tup . get ( i - 1 ) . index ) ; return ; } int T = tup . get ( i ) . r ; if ( T <= curr ) { System . out . print ( tup . get ( i ) . index + " ▁ " + currPos ) ; return ; } else { curr = T ; currPos = tup . get ( i ) . index ; } } System . out . print ( " - 1 ▁ - 1" ) ; } public static void main ( String [ ] args ) { int [ ] a = { 1 , 2 , 3 , 2 , 2 } ; int [ ] b = { 5 , 10 , 10 , 2 , 15 } ; int N = a . length ; findOverlapSegement ( N , a , b ) ; } }