Check if any K ranges overlap at any point | 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 ; 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
function kOverlap ( pairs , k ) { var vec = [ ] ; for ( var i = 0 ; i < pairs . length ; i ++ ) { vec . push ( [ pairs [ i ] [ 0 ] , - 1 ] ) ; vec . push ( [ pairs [ i ] [ 1 ] , + 1 ] ) ; } vec . sort ( ( a , b ) => { if ( a [ 0 ] != b [ 0 ] ) return a [ 0 ] - b [ 0 ] return a [ 1 ] - b [ 1 ] } ) ; var st = [ ] ; for ( var i = 0 ; i < vec . length ; i ++ ) { var cur = vec [ i ] ; if ( cur [ 1 ] == - 1 ) { st . push ( cur ) ; } else { st . pop ( ) ; } if ( st . length >= k ) { return true ; } } return false ; } var pairs = [ ] ; pairs . push ( [ 1 , 3 ] ) ; pairs . push ( [ 2 , 4 ] ) ; pairs . push ( [ 3 , 5 ] ) ; pairs . push ( [ 7 , 10 ] ) ; var n = pairs . length , k = 3 ; if ( kOverlap ( pairs , k ) ) document . write ( " " ) ; else document . write ( " " ) ;