Dados muchos intervalos como rangos y nuestra posición. Necesitamos encontrar la distancia mínima a recorrer para llegar a un punto que cubra todos los intervalos a la vez.
Ejemplos:
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.
Podemos resolver este problema concentrándonos únicamente en los puntos finales. Dado que el requisito es cubrir todos los intervalos alcanzando un punto, todos los intervalos deben compartir un punto para que exista la respuesta. Incluso el intervalo con el punto final más a la izquierda debe superponerse con el punto inicial del intervalo más a la derecha.
Primero encontramos el punto inicial más a la derecha y el punto final más a la izquierda de todos los intervalos. Luego podemos comparar nuestra posición con estos puntos para obtener el resultado que se explica a continuación:
- Si este punto inicial más a la derecha está a la derecha del punto final más a la izquierda, entonces no es posible cubrir todos los intervalos simultáneamente. (como en el ejemplo 2)
- Si nuestra posición está en el medio entre el inicio más a la derecha y el final más a la izquierda, entonces no hay necesidad de viajar y todos los intervalos estarán cubiertos solo por la posición actual (como en el ejemplo 3).
- Si nuestra posición es a la izquierda en ambos puntos, entonces debemos viajar hasta el punto inicial más a la derecha y si nuestra posición es a la derecha en ambos puntos, entonces debemos viajar hasta el punto final más a la izquierda.
Consulte el diagrama anterior para comprender estos casos. Como en el primer ejemplo, el inicio más a la derecha es 4 y el extremo más a la izquierda es 6, por lo que debemos llegar a 4 desde la posición actual 3 para cubrir todos los intervalos.
Consulte el siguiente código para una mejor comprensión.
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>
Producción:
1
Complejidad del tiempo: EN)
Espacio Auxiliar: EN)