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
// 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
# 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# 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
<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)