Minimális megtehető távolság az összes intervallum megtételéhez
Adott sok intervallum tartományként és pozíciónkként. Meg kell találnunk a minimális utazási távolságot, hogy elérjük azt a pontot, amely egyszerre lefedi az összes intervallumot.
Példák:
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.
Ezt a problémát úgy tudjuk megoldani, ha csak a végpontokra koncentrálunk. Mivel a követelmény az, hogy minden intervallumot le kell fedni egy pont elérésével, minden intervallumnak meg kell osztania egy pontot a válasz létezéséhez. Még a bal szélső végponttal rendelkező intervallumnak is át kell fednie a jobb szélső kezdőponttal.
Először minden intervallumból megtaláljuk a jobb oldali kezdőpontot és a bal szélső végpontot. Ezután összehasonlíthatjuk helyzetünket ezekkel a pontokkal, hogy megkapjuk az alábbiakban ismertetett eredményt:
- Ha ez a jobb oldali kezdőpont a bal szélső végponttól jobbra van, akkor nem lehetséges az összes intervallum egyidejű lefedése. (mint a 2. példában)
- Ha a pozíciónk középen van a jobb és a bal legvége között, akkor nincs szükség utazásra, és minden intervallumot csak az aktuális pozíció fed le (mint a 3. példában).
- Ha a pozíciónk mindkét pontban balra van, akkor fel kell utaznunk a jobb szélső kezdőpontra, ha pedig mindkét pontra jobbra esik, akkor a bal szélső végpontig kell utaznunk.
Az esetek megértéséhez tekintse meg a fenti diagramot. Mint az első példában, a jobb oldali eleje 4, a bal széle pedig a 6, így a jelenlegi 3-as pozícióból a 4-et kell elérnünk, hogy minden intervallumot lefedjünk.
Kérjük, olvassa el az alábbi kódot a jobb megértés érdekében.
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>
Kimenet:
1
Időbeli összetettség: ON)
Kiegészítő tér: ON)
