Minimální vzdálenost k překonání všech intervalů
Vzhledem k mnoha intervalům jako rozsahům a naší pozici. Musíme najít minimální vzdálenost, kterou musíme urazit, abychom dosáhli takového bodu, který pokryje všechny intervaly najednou.
Pří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 vyřešit tím, že se soustředíme pouze na koncové body. Protože požadavkem je pokrýt všechny intervaly dosažením bodu, musí všechny intervaly sdílet bod, aby existovala odpověď. I interval s krajním levým koncovým bodem se musí překrývat s intervalem zcela vpravo počátečním bodem.
Nejprve najdeme pravý počáteční bod a krajní levý konečný bod ze všech intervalů. Poté můžeme porovnat naši pozici s těmito body a získat výsledek, který je vysvětlen níže:
- Pokud je tento počáteční bod nejvíce vpravo napravo od krajního levého koncového bodu, pak není možné pokrýt všechny intervaly současně. (jako v příkladu 2)
- Pokud je naše pozice uprostřed mezi začátkem nejvíce vpravo a koncem nejvíce vlevo, není třeba cestovat a všechny intervaly budou pokryty pouze aktuální pozicí (jako v příkladu 3)
- Pokud je naše pozice vlevo u obou bodů, pak musíme cestovat nahoru k počátečnímu bodu nejvíce vpravo a pokud je naše pozice vpravo k oběma bodům, musíme cestovat nahoru do koncového bodu nejvíce vlevo.
Pro pochopení těchto případů se podívejte na výše uvedený diagram. Stejně jako v prvním příkladu je začátek nejvíce vpravo 4 a konec nejvíce vlevo je 6, takže potřebujeme dosáhnout 4 z aktuální pozice 3, abychom pokryli všechny intervaly.
Pro lepší pochopení se podívejte na níže 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á náročnost: NA)
Pomocný prostor: NA)
