Teniendo en cuenta tantos intervalos como rangos y nuestra posición. Necesitamos encontrar la distancia mínima a recorrer para llegar a tal 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 traveling
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 solo en los puntos finales. Dado que el requisito es cubrir todos los intervalos al llegar a un punto, todos los intervalos deben compartir un punto para que exista una respuesta. Incluso el intervalo con el punto final más a la izquierda debe superponerse con el punto de inicio más a la derecha del intervalo.
Primero, encontramos el punto de inicio 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 de inicio 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 se deja en ambos puntos, entonces debemos viajar hasta el punto de inicio 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 final más a la izquierda es 6, por lo que necesitamos llegar a 4 desde la posición actual 3 para cubrir todos los intervalos.
Por favor, consulte el siguiente código para una mejor comprensión.
C++
// C++ program to find minimum distance to
// travel to cover all intervals
#include <bits/stdc++.h>
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 intervals\n");
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 intervals\n");
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","<br>")
else
document.write(res)
// This code is contributed by shinjanpatra
</script>
Producción:
1
Complejidad de tiempo: O(N)
Espacio auxiliar: O(N)
Este artículo es una contribución de Utkarsh Trivedi . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA