Check if any K ranges overlap at any point | Java implementation of the approach ; Function that returns true if any k segments overlap at any point ; Vector to store the starting point and the ending point ; Starting points are marked by - 1 and ending points by + 1 ; Sort the vector by first element ; Comparator to sort the vector of pairs ; Stack to store the overlaps ; Get the current element ; If it is the starting point ; Push it in the stack ; It is the ending point ; Pop an element from stack ; If more than k ranges overlap ; Driver code
import java . util . ArrayList ; import java . util . Collections ; import java . util . Comparator ; import java . util . Stack ; class GFG { static class Pair { int first , second ; public Pair ( int first , int second ) { this . first = first ; this . second = second ; } } static boolean kOverlap ( ArrayList < Pair > pairs , int k ) { ArrayList < Pair > vec = new ArrayList < > ( ) ; for ( int i = 0 ; i < pairs . size ( ) ; i ++ ) { vec . add ( new Pair ( pairs . get ( i ) . first , - 1 ) ) ; vec . add ( new Pair ( pairs . get ( i ) . second , + 1 ) ) ; } Collections . sort ( vec , new Comparator < Pair > ( ) { public int compare ( Pair a , Pair b ) { if ( a . first != b . first ) return a . first - b . first ; return ( a . second - b . second ) ; } } ) ; Stack < Pair > st = new Stack < > ( ) ; for ( int i = 0 ; i < vec . size ( ) ; i ++ ) { Pair cur = vec . get ( i ) ; if ( cur . second == - 1 ) { st . push ( cur ) ; } else { st . pop ( ) ; } if ( st . size ( ) >= k ) { return true ; } } return false ; } public static void main ( String [ ] args ) { ArrayList < Pair > pairs = new ArrayList < > ( ) ; pairs . add ( new Pair ( 1 , 3 ) ) ; pairs . add ( new Pair ( 2 , 4 ) ) ; pairs . add ( new Pair ( 3 , 5 ) ) ; pairs . add ( new Pair ( 7 , 10 ) ) ; int n = pairs . size ( ) , k = 3 ; if ( kOverlap ( pairs , k ) ) System . out . println ( " Yes " ) ; else System . out . println ( " No " ) ; } }