Минимално разстояние за пътуване за покриване на всички интервали
Дадени са много интервали като диапазони и нашата позиция. Трябва да намерим минималното разстояние, което да изминем, за да достигнем такава точка, която покрива всички интервали наведнъж.
Примери:
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.
Можем да разрешим този проблем, като се концентрираме само върху крайните точки. Тъй като изискването е да се покрият всички интервали чрез достигане на точка, всички интервали трябва да споделят една точка, за да съществува отговор. Дори интервалът с най-лявата крайна точка трябва да се припокрива с най-дясната начална точка на интервала.
Първо намираме най-дясната начална точка и най-лявата крайна точка от всички интервали. След това можем да сравним нашата позиция с тези точки, за да получим резултата, който е обяснен по-долу:
- Ако тази най-дясна начална точка е вдясно от най-лявата крайна точка, тогава не е възможно да се покрият всички интервали едновременно. (както в пример 2)
- Ако позицията ни е по средата между най-десния начален и най-левия край, тогава няма нужда да пътуваме и всички интервали ще бъдат покрити само от текущата позиция (както в пример 3)
- Ако нашата позиция е вляво към двете точки, тогава трябва да пътуваме до най-дясната начална точка и ако нашата позиция е вдясно към двете точки, тогава трябва да пътуваме до най-лявата крайна точка.
Вижте диаграмата по-горе, за да разберете тези случаи. Както в първия пример най-дясното начало е 4, а най-левият край е 6, така че трябва да достигнем 4 от текущата позиция 3, за да покрием всички интервали.
Моля, вижте кода по-долу за по-добро разбиране.
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>
Изход:
1
Времева сложност: O(N)
Помощно пространство: O(N)
