Dati molti intervalli come intervalli e la nostra posizione. Dobbiamo trovare la distanza minima da percorrere per raggiungere un punto tale che copra tutti gli intervalli contemporaneamente.
Esempi:
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.
Possiamo risolvere questo problema concentrandoci solo sugli endpoint. Poiché il requisito è quello di coprire tutti gli intervalli raggiungendo un punto, tutti gli intervalli devono condividere un punto affinché esista una risposta. Anche l'intervallo con il punto finale più a sinistra deve sovrapporsi al punto iniziale dell'intervallo più a destra.
Per prima cosa troviamo il punto iniziale più a destra e il punto finale più a sinistra da tutti gli intervalli. Quindi possiamo confrontare la nostra posizione con questi punti per ottenere il risultato spiegato di seguito:
- Se il punto iniziale più a destra si trova a destra del punto finale più a sinistra, non è possibile coprire tutti gli intervalli contemporaneamente. (come nell'esempio 2)
- Se la nostra posizione è a metà tra l'inizio più a destra e l'estremità più a sinistra, non è necessario viaggiare e tutti gli intervalli saranno coperti solo dalla posizione corrente (come nell'esempio 3)
- Se la nostra posizione è a sinistra rispetto a entrambi i punti, allora dobbiamo viaggiare fino al punto iniziale più a destra e se la nostra posizione è a destra rispetto a entrambi i punti, allora dobbiamo viaggiare fino al punto finale più a sinistra.
Fare riferimento al diagramma sopra per comprendere questi casi. Poiché nel primo esempio l'inizio più a destra è 4 e l'estremità più a sinistra è 6, quindi dobbiamo raggiungere 4 dalla posizione attuale 3 per coprire tutti gli intervalli.
Si prega di consultare il codice seguente per una migliore comprensione.
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>
Produzione:
1
Complessità temporale: SU)
Spazio ausiliario: SU)