Un intervalo se representa como una combinación de la hora de inicio y la hora de finalización. Dado un conjunto de intervalos, verifique si dos intervalos se cruzan.
Ejemplos:
Input: arr[] = {{1, 3}, {5, 7}, {2, 4}, {6, 8}}
Output: true
The intervals {1, 3} and {2, 4} overlap
Input: arr[] = {{1, 3}, {7, 9}, {4, 6}, {10, 13}}
Output: false
No pair of intervals overlap.
La complejidad de tiempo esperada es O(nLogn) donde n es el número de intervalos.
Recomendamos encarecidamente minimizar su navegador y probarlo usted mismo primero.
Una solución simple es considerar cada par de intervalos y verificar si el par se cruza o no. La complejidad temporal de esta solución es O(n 2 )
Método 1
Una mejor solución es usar la clasificación . El siguiente es el algoritmo completo.
1) Ordene todos los intervalos en orden creciente de tiempo de inicio. Este paso toma tiempo O(nLogn).
2) En la array ordenada, si el tiempo de inicio de un intervalo es menor que el final del intervalo anterior, entonces hay una superposición. Este paso toma tiempo O(n).
Entonces, la complejidad de tiempo general del algoritmo es O (nLogn) + O (n), que es O (nLogn).
A continuación se muestra la implementación de la idea anterior.
C++
// A C++ program to check if any two intervals overlap
#include <algorithm>
#include <iostream>
using namespace std;
// An interval has start time and end time
struct Interval {
int start;
int end;
};
// Compares two intervals according to their starting time.
// This is needed for sorting the intervals using library
// function std::sort(). See http:// goo.gl/iGspV
bool compareInterval(Interval i1, Interval i2)
{
return (i1.start < i2.start) ? true : false;
}
// Function to check if any two intervals overlap
bool isIntersect(Interval arr[], int n)
{
// Sort intervals in increasing order of start time
sort(arr, arr + n , compareInterval);
// In the sorted array, if start time of an interval
// is less than end of previous interval, then there
// is an overlap
for (int i = 1; i < n; i++)
if (arr[i - 1].end > arr[i].start)
return true;
// If we reach here, then no overlap
return false;
}
// Driver program
int main()
{
Interval arr1[] = { { 1, 3 }, { 7, 9 }, { 4, 6 }, { 10, 13 } };
int n1 = sizeof(arr1) / sizeof(arr1[0]);
isIntersect(arr1, n1) ? cout << "Yes\n" : cout << "No\n";
Interval arr2[] = { { 6, 8 }, { 1, 3 }, { 2, 4 }, { 4, 7 } };
int n2 = sizeof(arr2) / sizeof(arr2[0]);
isIntersect(arr2, n2) ? cout << "Yes\n" : cout << "No\n";
return 0;
}
Java
// A Java program to check if any two intervals overlap
import java.io.*;
import java.lang.*;
import java.util.*;
class GFG{
// An interval has start time and end time
static class Interval
{
int start;
int end;
public Interval(int start, int end)
{
super();
this.start = start;
this.end = end;
}
};
// Function to check if any two intervals overlap
static boolean isIntersect(Interval arr[], int n)
{
// Sort intervals in increasing order of start time
Arrays.sort(arr, (i1, i2) -> {
return i1.start - i2.start;
});
// In the sorted array, if start time of an interval
// is less than end of previous interval, then there
// is an overlap
for(int i = 1; i < n; i++)
if (arr[i - 1].end > arr[i].start)
return true;
// If we reach here, then no overlap
return false;
}
// Driver code
public static void main(String[] args)
{
Interval arr1[] = { new Interval(1, 3),
new Interval(7, 9),
new Interval(4, 6),
new Interval(10, 13) };
int n1 = arr1.length;
if (isIntersect(arr1, n1))
System.out.print("Yes\n");
else
System.out.print("No\n");
Interval arr2[] = { new Interval(6, 8),
new Interval(1, 3),
new Interval(2, 4),
new Interval(4, 7) };
int n2 = arr2.length;
if (isIntersect(arr2, n2))
System.out.print("Yes\n");
else
System.out.print("No\n");
}
}
// This code is contributed by Kingash
Python3
# A Python program to check if any two intervals overlap
# An interval has start time and end time
class Interval:
def __init__(self, start, end):
self.start = start
self.end = end
# Function to check if any two intervals overlap
def isIntersect(arr, n):
# Sort intervals in increasing order of start time
arr.sort(key=lambda x: x.start)
# In the sorted array, if start time of an interval
# is less than end of previous interval, then there
# is an overlap
for i in range(1, n):
if (arr[i - 1].end > arr[i].start):
return True
# If we reach here, then no overlap
return False
# Driver code
arr1 = [Interval(1, 3), Interval(7, 9), Interval(4, 6), Interval(10, 13)]
n1 = len(arr1)
if (isIntersect(arr1, n1)):
print("Yes")
else:
print("No")
arr2 = [Interval(6, 8), Interval(1, 3), Interval(2, 4), Interval(4, 7)]
n2 = len(arr2)
if (isIntersect(arr2, n2)):
print("Yes")
else:
print("No")
# This code is contributed by Saurabh Jaiswal
Javascript
<script>
// A Javascript program to check if any two intervals overlap
// An interval has start time and end time
class Interval
{
constructor(start,end)
{
this.start = start;
this.end = end;
}
}
// Function to check if any two intervals overlap
function isIntersect(arr,n)
{
// Sort intervals in increasing order of start time
arr.sort(function(i1, i2){
return i1.start - i2.start;
});
// In the sorted array, if start time of an interval
// is less than end of previous interval, then there
// is an overlap
for(let i = 1; i < n; i++)
if (arr[i - 1].end > arr[i].start)
return true;
// If we reach here, then no overlap
return false;
}
// Driver code
let arr1=[new Interval(1, 3),
new Interval(7, 9),
new Interval(4, 6),
new Interval(10, 13) ];
let n1 = arr1.length;
if (isIntersect(arr1, n1))
document.write("Yes<br>");
else
document.write("No<br>");
let arr2 = [ new Interval(6, 8),
new Interval(1, 3),
new Interval(2, 4),
new Interval(4, 7) ];
let n2 = arr2.length;
if (isIntersect(arr2, n2))
document.write("Yes<br>");
else
document.write("No<br>");
// This code is contributed by rag2127
</script>
Producción:
No Yes
Complejidad de tiempo: O (nlogn)
Espacio Auxiliar : O(1)
Método 2 : Anjali Agarwal sugiere este enfoque . Los siguientes son los pasos:
1. Encuentre el elemento máximo general. Sea max_ele
2. Inicialice una array de tamaño max_ele con 0.
3. Para cada intervalo [inicio, fin], incremente el valor en el inicio del índice, es decir, arr[inicio]++ y disminuya el valor en el índice (fin + 1 ), es decir arr[fin + 1]- -.
4. Calcule la suma de prefijos de esta array (arr[]).
5. Cada índice, i de esta array de suma de prefijos dirá cuántas veces i ha ocurrido en todos los intervalos tomados juntos. Si este valor es mayor que 1, entonces ocurre en 2 o más intervalos.
6. Entonces, simplemente inicialice la variable de resultado como falsa y mientras recorre la array de suma de prefijos, cambie la variable de resultado a verdadera siempre que el valor en ese índice sea mayor que 1.
A continuación se muestra la implementación de este enfoque (Método 2).
C++
// A C++ program to check if any two intervals overlap
#include <algorithm>
#include <iostream>
using namespace std;
// An interval has start time and end time
struct Interval {
int start;
int end;
};
// Function to check if any two intervals overlap
bool isIntersect(Interval arr[], int n)
{
int max_ele = 0;
// Find the overall maximum element
for (int i = 0; i < n; i++) {
if (max_ele < arr[i].end)
max_ele = arr[i].end;
}
// Initialize an array of size max_ele
int aux[max_ele + 1] = { 0 };
for (int i = 0; i < n; i++) {
// starting point of the interval
int x = arr[i].start;
// end point of the interval
int y = arr[i].end;
aux[x]++, aux[y + 1]--;
}
for (int i = 1; i <= max_ele; i++) {
// Calculating the prefix Sum
aux[i] += aux[i - 1];
// Overlap
if (aux[i] > 1)
return true;
}
// If we reach here, then no Overlap
return false;
}
// Driver program
int main()
{
Interval arr1[] = { { 1, 3 }, { 7, 9 }, { 4, 6 }, { 10, 13 } };
int n1 = sizeof(arr1) / sizeof(arr1[0]);
isIntersect(arr1, n1) ? cout << "Yes\n" : cout << "No\n";
Interval arr2[] = { { 6, 8 }, { 1, 3 }, { 2, 4 }, { 4, 7 } };
int n2 = sizeof(arr2) / sizeof(arr2[0]);
isIntersect(arr2, n2) ? cout << "Yes\n" : cout << "No\n";
return 0;
}
// This Code is written by Anjali Agarwal
Java
// A Java program to check if any two intervals overlap
class GFG
{
// An interval has start time and end time
static class Interval
{
int start;
int end;
public Interval(int start, int end)
{
super();
this.start = start;
this.end = end;
}
};
// Function to check if any two intervals overlap
static boolean isIntersect(Interval arr[], int n)
{
int max_ele = 0;
// Find the overall maximum element
for (int i = 0; i < n; i++)
{
if (max_ele < arr[i].end)
max_ele = arr[i].end;
}
// Initialize an array of size max_ele
int []aux = new int[max_ele + 1];
for (int i = 0; i < n; i++)
{
// starting point of the interval
int x = arr[i].start;
// end point of the interval
int y = arr[i].end;
aux[x]++;
aux[y ]--;
}
for (int i = 1; i <= max_ele; i++)
{
// Calculating the prefix Sum
aux[i] += aux[i - 1];
// Overlap
if (aux[i] > 1)
return true;
}
// If we reach here, then no Overlap
return false;
}
// Driver program
public static void main(String[] args)
{
Interval arr1[] = { new Interval(1, 3), new Interval(7, 9),
new Interval(4, 6), new Interval(10, 13) };
int n1 = arr1.length;
if(isIntersect(arr1, n1))
System.out.print("Yes\n");
else
System.out.print("No\n");
Interval arr2[] = { new Interval(6, 8), new Interval(1, 3),
new Interval(2, 4), new Interval(4, 7) };
int n2 = arr2.length;
if(isIntersect(arr2, n2))
System.out.print("Yes\n");
else
System.out.print("No\n");
}
}
// This code is contributed by 29AjayKumar
C#
// C# program to check if
// any two intervals overlap
using System;
class GFG
{
// An interval has start time and end time
class Interval
{
public int start;
public int end;
public Interval(int start, int end)
{
this.start = start;
this.end = end;
}
};
// Function to check if
// any two intervals overlap
static bool isIntersect(Interval []arr, int n)
{
int max_ele = 0;
// Find the overall maximum element
for (int i = 0; i < n; i++)
{
if (max_ele < arr[i].end)
max_ele = arr[i].end;
}
// Initialize an array of size max_ele
int []aux = new int[max_ele + 1];
for (int i = 0; i < n; i++)
{
// starting point of the interval
int x = arr[i].start;
// end point of the interval
int y = arr[i].end;
aux[x]++;
aux[y ]--;
}
for (int i = 1; i <= max_ele; i++)
{
// Calculating the prefix Sum
aux[i] += aux[i - 1];
// Overlap
if (aux[i] > 1)
return true;
}
// If we reach here, then no Overlap
return false;
}
// Driver Code
public static void Main(String[] args)
{
Interval []arr1 = { new Interval(1, 3),
new Interval(7, 9),
new Interval(4, 6),
new Interval(10, 13) };
int n1 = arr1.Length;
if(isIntersect(arr1, n1))
Console.Write("Yes\n");
else
Console.Write("No\n");
Interval []arr2 = { new Interval(6, 8),
new Interval(1, 3),
new Interval(2, 4),
new Interval(4, 7) };
int n2 = arr2.Length;
if(isIntersect(arr2, n2))
Console.Write("Yes\n");
else
Console.Write("No\n");
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// A Javascript program to check if any two intervals overlap
// An interval has start time and end time
class Interval
{
constructor(start, end)
{
this.start = start;
this.end = end;
}
}
// Function to check if any two intervals overlap
function isIntersect(arr, n)
{
let max_ele = 0;
// Find the overall maximum element
for (let i = 0; i < n; i++)
{
if (max_ele < arr[i].end)
max_ele = arr[i].end;
}
// Initialize an array of size max_ele
let aux = new Array(max_ele + 1);
for(let i=0;i<(max_ele + 1);i++)
{
aux[i]=0;
}
for (let i = 0; i < n; i++)
{
// starting point of the interval
let x = arr[i].start;
// end point of the interval
let y = arr[i].end;
aux[x]++;
aux[y ]--;
}
for (let i = 1; i <= max_ele; i++)
{
// Calculating the prefix Sum
aux[i] += aux[i - 1];
// Overlap
if (aux[i] > 1)
return true;
}
// If we reach here, then no Overlap
return false;
}
// Driver program
let arr1 = [new Interval(1, 3), new Interval(7, 9),
new Interval(4, 6), new Interval(10, 13)];
let n1 = arr1.length;
if(isIntersect(arr1, n1))
document.write("Yes<br>");
else
document.write("No<br>");
let arr2 = [ new Interval(6, 8), new Interval(1, 3),
new Interval(2, 4), new Interval(4, 7) ];
let n2 = arr2.length;
if(isIntersect(arr2, n2))
document.write("Yes<br>");
else
document.write("No<br>");
// This code is contributed by avanitrachhadiya2155
</script>
Producción:
No Yes
Complejidad de tiempo: O (max_ele + n)
Espacio Auxiliar : O(max_ele)
Nota: Este método es más eficiente que el Método 1 si hay más intervalos y, al mismo tiempo, el valor máximo entre todos los intervalos debe ser bajo, ya que la complejidad del tiempo es directamente proporcional a O(max_ele).
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