Find a pair of intersecting ranges from a given array | C ++ program for the above approach ; Store ranges and their corresponding array indices ; Function to find a pair of intersecting ranges ; Stores ending point of every range ; Stores the maximum ending point obtained ; Iterate from 0 to N - 1 ; Starting point of the current range ; End point of the current range ; Push pairs into tup ; Sort the tup vector ; Iterate over the ranges ; If starting points are equal ; Print the indices of the intersecting ranges ; If no such pair of segments exist ; Driver Code ; Given N ; Given 2d ranges [ ] [ ] array ; Function call
#include <bits/stdc++.h> NEW_LINE using namespace std ; vector < pair < pair < int , int > , int > > tup ; void findIntersectingRange ( int N , int ranges [ ] [ 2 ] ) { int curr ; int currPos ; for ( int i = 0 ; i < N ; i ++ ) { int x , y ; x = ranges [ i ] [ 0 ] ; y = ranges [ i ] [ 1 ] ; tup . push_back ( { { x , y } , i + 1 } ) ; } sort ( tup . begin ( ) , tup . end ( ) ) ; curr = tup [ 0 ] . first . second ; 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 N = 5 ; int ranges [ ] [ 2 ] = { { 1 , 5 } , { 2 , 10 } , { 3 , 10 } , { 2 , 2 } , { 2 , 15 } } ; findIntersectingRange ( N , ranges ) ; }