Dados muitos intervalos como intervalos e nossa posição. Precisamos encontrar a distância mínima a percorrer para chegar a um ponto que cubra todos os intervalos de uma vez.
Exemplos:
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 concentrando-nos apenas nos pontos finais. Como o requisito é cobrir todos os intervalos atingindo um ponto, todos os intervalos devem compartilhar um ponto para que a resposta exista. Mesmo o intervalo com o ponto final mais à esquerda deve se sobrepor ao ponto inicial do intervalo mais à direita.
Primeiro encontramos o ponto inicial mais à direita e o ponto final mais à esquerda de todos os intervalos. Então podemos comparar nossa posição com esses pontos para obter o resultado que é explicado abaixo:
- Se este ponto inicial mais à direita estiver à direita do ponto final mais à esquerda, não será possível cobrir todos os intervalos simultaneamente. (como no exemplo 2)
- Se a nossa posição estiver no meio entre o início mais à direita e o final mais à esquerda, então não há necessidade de viajar e todos os intervalos serão cobertos apenas pela posição atual (como no exemplo 3)
- Se a nossa posição for à esquerda de ambos os pontos, precisaremos de viajar até ao ponto inicial mais à direita e se a nossa posição for à direita de ambos os pontos, então precisaremos de viajar até ao ponto final mais à esquerda.
Consulte o diagrama acima para entender esses casos. Como no primeiro exemplo, o início mais à direita é 4 e o final mais à esquerda é 6, então precisamos chegar a 4 a partir da posição atual 3 para cobrir todos os intervalos.
Por favor, veja o código abaixo para uma melhor compreensão.
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>
Saída:
1
Complexidade de tempo: SOBRE)
Espaço Auxiliar: SOBRE)