Minimálna vzdialenosť na pokrytie všetkých intervalov
Vzhľadom na veľa intervalov ako rozsahy a našu pozíciu. Musíme nájsť minimálnu vzdialenosť, ktorú musíme prejsť, aby sme dosiahli taký bod, ktorý pokrýva všetky intervaly naraz.
Príklady:
Input : Intervals = [(0 7) (2 14) (4 6)] Position = 3 Output : 1 We can reach position 4 by travelling distance 1 at which all intervals will be covered. So answer will be 1 Input : Intervals = [(1 2) (2 3) (3 4)] Position = 2 Output : -1 It is not possible to cover all intervals at once at any point Input : Intervals = [(1 2) (2 3) (1 4)] Position = 2 Output : 0 All Intervals are covered at current position only so no need travel and answer will be 0 All above examples are shown in below diagram.
Tento problém môžeme vyriešiť sústredením sa len na koncové body. Keďže požiadavkou je pokryť všetky intervaly dosiahnutím bodu, všetky intervaly musia zdieľať bod, aby mohla existovať odpoveď. Dokonca aj interval s koncovým bodom úplne vľavo sa musí prekrývať s intervalom začiatočným bodom úplne vpravo.
Najprv nájdeme pravý počiatočný bod a krajný ľavý koncový bod zo všetkých intervalov. Potom môžeme porovnať našu pozíciu s týmito bodmi a získať výsledok, ktorý je vysvetlený nižšie:
- Ak sa tento začiatočný bod najviac vpravo nachádza napravo od krajného ľavého koncového bodu, potom nie je možné pokryť všetky intervaly súčasne. (ako v príklade 2)
- Ak je naša pozícia v strede medzi začiatkom úplne vpravo a úplne vľavo, potom nie je potrebné cestovať a všetky intervaly budú pokryté iba aktuálnou pozíciou (ako v príklade 3)
- Ak je naša pozícia ponechaná k obom bodom, potom musíme cestovať až k počiatočnému bodu úplne vpravo a ak je naša pozícia vpravo k obom bodom, musíme cestovať až do krajného ľavého koncového bodu.
Pozrite si vyššie uvedený diagram, aby ste pochopili tieto prípady. Keďže v prvom príklade je začiatok úplne vpravo 4 a koniec vľavo je 6, takže musíme dosiahnuť 4 z aktuálnej pozície 3, aby sme pokryli všetky intervaly.
Pre lepšie pochopenie si pozrite nižšie uvedený kód.
C++ // C++ program to find minimum distance to // travel to cover all intervals #include using namespace std ; // structure to store an interval struct Interval { int start end ; Interval ( int start int end ) : start ( start ) end ( end ) {} }; // Method returns minimum distance to travel // to cover all intervals int minDistanceToCoverIntervals ( Interval intervals [] int N int x ) { int rightMostStart = INT_MIN ; int leftMostEnd = INT_MAX ; // looping over all intervals to get right most // start and left most end for ( int i = 0 ; i < N ; i ++ ) { if ( rightMostStart < intervals [ i ]. start ) rightMostStart = intervals [ i ]. start ; if ( leftMostEnd > intervals [ i ]. end ) leftMostEnd = intervals [ i ]. end ; } int res ; /* if rightmost start > leftmost end then all intervals are not aligned and it is not possible to cover all of them */ if ( rightMostStart > leftMostEnd ) res = -1 ; // if x is in between rightmoststart and // leftmostend then no need to travel any distance else if ( rightMostStart <= x && x <= leftMostEnd ) res = 0 ; // choose minimum according to current position x else res = ( x < rightMostStart ) ? ( rightMostStart - x ) : ( x - leftMostEnd ); return res ; } // Driver code to test above methods int main () { int x = 3 ; Interval intervals [] = {{ 0 7 } { 2 14 } { 4 6 }}; int N = sizeof ( intervals ) / sizeof ( intervals [ 0 ]); int res = minDistanceToCoverIntervals ( intervals N x ); if ( res == -1 ) cout < < 'Not Possible to cover all intervals n ' ; else cout < < res < < endl ; }
Java // Java program to find minimum distance // to travel to cover all intervals import java.util.* ; class GFG { // Structure to store an interval static class Interval { int start end ; Interval ( int start int end ) { this . start = start ; this . end = end ; } }; // Method returns minimum distance to // travel to cover all intervals static int minDistanceToCoverIntervals ( Interval intervals [] int N int x ) { int rightMostStart = Integer . MIN_VALUE ; int leftMostEnd = Integer . MAX_VALUE ; // Looping over all intervals to get // right most start and left most end for ( int i = 0 ; i < N ; i ++ ) { if ( rightMostStart < intervals [ i ] . start ) rightMostStart = intervals [ i ] . start ; if ( leftMostEnd > intervals [ i ] . end ) leftMostEnd = intervals [ i ] . end ; } int res ; // If rightmost start > leftmost end then // all intervals are not aligned and it // is not possible to cover all of them if ( rightMostStart > leftMostEnd ) res = - 1 ; // If x is in between rightmoststart and // leftmostend then no need to travel // any distance else if ( rightMostStart <= x && x <= leftMostEnd ) res = 0 ; // Choose minimum according to // current position x else res = ( x < rightMostStart ) ? ( rightMostStart - x ) : ( x - leftMostEnd ); return res ; } // Driver code public static void main ( String [] args ) { int x = 3 ; Interval [] intervals = { new Interval ( 0 7 ) new Interval ( 2 14 ) new Interval ( 4 6 ) }; int N = intervals . length ; int res = minDistanceToCoverIntervals ( intervals N x ); if ( res == - 1 ) System . out . print ( 'Not Possible to ' + 'cover all intervalsn' ); else System . out . print ( res + 'n' ); } } // This code is contributed by Rajput-Ji
Python3 # Python program to find minimum distance to # travel to cover all intervals # Method returns minimum distance to travel # to cover all intervals def minDistanceToCoverIntervals ( Intervals N x ): rightMostStart = Intervals [ 0 ][ 0 ] leftMostStart = Intervals [ 0 ][ 1 ] # looping over all intervals to get right most # start and left most end for curr in Intervals : if rightMostStart < curr [ 0 ]: rightMostStart = curr [ 0 ] if leftMostStart > curr [ 1 ]: leftMostStart = curr [ 1 ] # if rightmost start > leftmost end then all # intervals are not aligned and it is not # possible to cover all of them if rightMostStart > leftMostStart : res = - 1 # if x is in between rightmoststart and # leftmostend then no need to travel any distance else if rightMostStart <= x and x <= leftMostStart : res = 0 # choose minimum according to current position x else : res = rightMostStart - x if x < rightMostStart else x - leftMostStart return res # Driver code to test above methods Intervals = [[ 0 7 ] [ 2 14 ] [ 4 6 ]] N = len ( Intervals ) x = 3 res = minDistanceToCoverIntervals ( Intervals N x ) if res == - 1 : print ( 'Not Possible to cover all intervals' ) else : print ( res ) # This code is contributed by rj13to.
C# // C# program to find minimum distance // to travel to cover all intervals using System ; class GFG { // Structure to store an interval public class Interval { public int start end ; public Interval ( int start int end ) { this . start = start ; this . end = end ; } }; // Method returns minimum distance to // travel to cover all intervals static int minDistanceToCoverIntervals ( Interval [] intervals int N int x ) { int rightMostStart = int . MinValue ; int leftMostEnd = int . MaxValue ; // Looping over all intervals to get // right most start and left most end for ( int i = 0 ; i < N ; i ++ ) { if ( rightMostStart < intervals [ i ]. start ) rightMostStart = intervals [ i ]. start ; if ( leftMostEnd > intervals [ i ]. end ) leftMostEnd = intervals [ i ]. end ; } int res ; // If rightmost start > leftmost end then // all intervals are not aligned and it // is not possible to cover all of them if ( rightMostStart > leftMostEnd ) res = - 1 ; // If x is in between rightmoststart and // leftmostend then no need to travel // any distance else if ( rightMostStart <= x && x <= leftMostEnd ) res = 0 ; // Choose minimum according to // current position x else res = ( x < rightMostStart ) ? ( rightMostStart - x ) : ( x - leftMostEnd ); return res ; } // Driver code public static void Main ( String [] args ) { int x = 3 ; Interval [] intervals = { new Interval ( 0 7 ) new Interval ( 2 14 ) new Interval ( 4 6 ) }; int N = intervals . Length ; int res = minDistanceToCoverIntervals ( intervals N x ); if ( res == - 1 ) Console . Write ( 'Not Possible to ' + 'cover all intervalsn' ); else Console . Write ( res + 'n' ); } } // This code is contributed by shikhasingrajput
JavaScript < script > // JavaScript program to find minimum distance to // travel to cover all intervals // Method returns minimum distance to travel // to cover all intervals function minDistanceToCoverIntervals ( Intervals N x ){ let rightMostStart = Intervals [ 0 ][ 0 ] let leftMostStart = Intervals [ 0 ][ 1 ] // looping over all intervals to get right most // start and left most end for ( let curr of Intervals ){ if ( rightMostStart < curr [ 0 ]) rightMostStart = curr [ 0 ] if ( leftMostStart > curr [ 1 ]) leftMostStart = curr [ 1 ] } let res ; // if rightmost start > leftmost end then all // intervals are not aligned and it is not // possible to cover all of them if ( rightMostStart > leftMostStart ) res = - 1 // if x is in between rightmoststart and // leftmostend then no need to travel any distance else if ( rightMostStart <= x && x <= leftMostStart ) res = 0 // choose minimum according to current position x else res = ( x < rightMostStart ) ? rightMostStart - x : x - leftMostStart return res } // Driver code to test above methods let Intervals = [[ 0 7 ] [ 2 14 ] [ 4 6 ]] let N = Intervals . length let x = 3 let res = minDistanceToCoverIntervals ( Intervals N x ) if ( res == - 1 ) document . write ( 'Not Possible to cover all intervals' '
' ) else document . write ( res ) // This code is contributed by shinjanpatra < /script>
výstup:
1
Časová zložitosť: O(N)
Pomocný priestor: O(N)
