Minimumsafstand at køre for at dække alle intervaller
Givet mange intervaller som intervaller og vores position. Vi skal finde minimumsafstanden for at nå et sådant punkt, som dækker alle intervaller på én gang.
Eksempler:
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.
Vi kan løse dette problem ved kun at koncentrere os om endepunkter. Da kravet er at dække alle intervaller ved at nå et punkt skal alle intervaller dele et punkt for at svaret eksisterer. Selv intervallet med slutpunktet længst til venstre skal overlappe med intervallet længst til højre startpunktet.
Først finder vi startpunktet længst til højre og slutpunktet længst til venstre fra alle intervaller. Så kan vi sammenligne vores position med disse punkter for at få resultatet, som er forklaret nedenfor:
- Hvis dette startpunkt længst til højre er til højre for slutpunktet længst til venstre, er det ikke muligt at dække alle intervaller samtidigt. (som i eksempel 2)
- Hvis vores position er midt mellem til højre mest start og venstre mest ende, er der ingen grund til at rejse, og alle intervaller vil kun blive dækket af den nuværende position (som i eksempel 3)
- Hvis vores position er tilbage til begge punkter, skal vi rejse op til startpunktet længst til højre, og hvis vores position er lige til begge punkter, skal vi rejse op til slutpunktet længst til venstre.
Se ovenstående diagram for at forstå disse tilfælde. Som i det første eksempel er højre mest start 4 og venstre yderste ende er 6, så vi skal nå 4 fra nuværende position 3 for at dække alle intervaller.
Se venligst nedenstående kode for en bedre forståelse.
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>
Produktion:
1
Tidskompleksitet: PÅ)
Hjælpeplads: PÅ)
