Dadas dos arrays 2-D que representan intervalos. Cada array 2-D representa una lista de intervalos. Cada lista de intervalos está separada y ordenada en orden creciente. Encuentre la intersección o conjunto de rangos que son comunes a ambas listas.
Disjunto significa que ningún elemento es común en una lista. Ejemplo: {1, 4} y {5, 6} son disjuntos, mientras que {1, 4} y {2, 5} no lo son, ya que 2, 3 y 4 son comunes a ambos intervalos.
Ejemplos:
Entrada: arr1[][] = {{0, 4}, {5, 10}, {13, 20}, {24, 25}}
arr2[][] = {{1, 5}, {8, 12 }, {15, 24}, {25, 26}}
Salida: {{1, 4}, {5, 5}, {8, 10}, {15, 20}, {24, 24}, {25, 25}}
Explicación:
{1, 4} se encuentra completamente dentro del rango {0, 4} y {1, 5}. Por lo tanto, {1, 4} es la intersección deseada. De manera similar, {24, 24} se encuentra completamente dentro de dos intervalos {24, 25} y {15, 24}.
Entrada: arr1[][] = {{0, 2}, {5, 10}, {12, 22}, {24, 25}}
arr2[][] = {{1, 4}, {9, 12 }, {15, 24}, {25, 26}}
Salida: {{1, 2}, {9, 10}, {12, 12}, {15, 22}, {24, 24}, {25, 25}}
Explicación:
{1, 2} se encuentra completamente dentro del rango {0, 2} y {1, 4}. Por lo tanto, {1, 2} es la intersección deseada. De manera similar, {12, 12} se encuentra completamente dentro de dos intervalos {12, 22} y {9, 12}.
Enfoque:
para resolver el problema mencionado anteriormente, se puede utilizar la técnica de dos punteros , según los pasos que se detallan a continuación:
- Mantenga dos punteros i y j para recorrer las dos listas de intervalos, arr1 y arr2 respectivamente.
- Ahora, si arr1[i] tiene el punto final más pequeño, solo puede cruzarse con arr2[j]. De manera similar, si arr2[j] tiene el punto final más pequeño, solo puede cruzarse con arr1[i]. Si se produce una intersección, encuentre el segmento de intersección.
- [l, r] será el segmento de intersección si y si l <= r, donde l = max(arr1[i][0], arr2[j][0]) y r = min(arr1[i][1], arr2[j][1]) .
- Incremente los punteros i y j en consecuencia para avanzar.
A continuación se muestra la implementación del enfoque:
C++
// C++ implementation to find the
// intersection of the two intervals
#include <bits/stdc++.h>
using namespace std;
// Function to print intersecting intervals
void printIntervals(vector<vector<int> > arr1,
vector<vector<int> > arr2)
{
// i and j pointers for
// arr1 and arr2 respectively
int i = 0, j = 0;
// Size of the two lists
int n = arr1.size(), m = arr2.size();
// Loop through all intervals unless
// one of the interval gets exhausted
while (i < n && j < m) {
// Left bound for intersecting segment
int l = max(arr1[i][0], arr2[j][0]);
// Right bound for intersecting segment
int r = min(arr1[i][1], arr2[j][1]);
// If segment is valid print it
if (l <= r)
cout << "{" << l << ", "
<< r << "}\n";
// If i-th interval's right
// bound is smaller
// increment i else
// increment j
if (arr1[i][1] < arr2[j][1])
i++;
else
j++;
}
}
// Driver code
int main()
{
vector<vector<int> > arr1
= { { 0, 4 }, { 5, 10 },
{ 13, 20 }, { 24, 25 } };
vector<vector<int> > arr2
= { { 1, 5 }, { 8, 12 },
{ 15, 24 }, { 25, 26 } };
printIntervals(arr1, arr2);
return 0;
}
Java
// Java implementation to find
// intersecting intervals
class GFG{
// Function to print intersecting intervals
static void printIntervals(int arr1[][],
int arr2[][])
{
// i and j pointers for arr1 and
// arr2 respectively
int i = 0, j = 0;
int n = arr1.length, m = arr2.length;
// Loop through all intervals unless
// one of the interval gets exhausted
while (i < n && j < m)
{
// Left bound for intersecting segment
int l = Math.max(arr1[i][0], arr2[j][0]);
// Right bound for intersecting segment
int r = Math.min(arr1[i][1], arr2[j][1]);
// If segment is valid print it
if (l <= r)
System.out.println("{" + l + ", " +
r + "}");
// If i-th interval's right bound is
// smaller increment i else increment j
if (arr1[i][1] < arr2[j][1])
i++;
else
j++;
}
}
// Driver code
public static void main(String[] args)
{
int arr1[][] = { { 0, 4 }, { 5, 10 },
{ 13, 20 }, { 24, 25 } };
int arr2[][] = { { 1, 5 }, { 8, 12 },
{ 15, 24 }, { 25, 26 } };
printIntervals(arr1, arr2);
}
}
// This code is contributed by sarthak_eddy
Python3
# Python3 implementation to find
# intersecting intervals
# Function to print intersecting
# intervals
def printIntervals(arr1, arr2):
# i and j pointers for arr1
# and arr2 respectively
i = j = 0
n = len(arr1)
m = len(arr2)
# Loop through all intervals unless one
# of the interval gets exhausted
while i < n and j < m:
# Left bound for intersecting segment
l = max(arr1[i][0], arr2[j][0])
# Right bound for intersecting segment
r = min(arr1[i][1], arr2[j][1])
# If segment is valid print it
if l <= r:
print('{', l, ',', r, '}')
# If i-th interval's right bound is
# smaller increment i else increment j
if arr1[i][1] < arr2[j][1]:
i += 1
else:
j += 1
# Driver code
arr1 = [ [ 0, 4 ], [ 5, 10 ],
[ 13, 20 ], [ 24, 25 ] ]
arr2 = [ [ 1, 5 ], [ 8, 12 ],
[ 15, 24 ], [ 25, 26 ] ]
printIntervals(arr1, arr2)
# This code is contributed by sarthak_eddy
C#
// C# implementation to find
// intersecting intervals
using System;
class GFG{
// Function to print intersecting intervals
static void printIntervals(int [,]arr1,
int [,]arr2)
{
// i and j pointers for arr1 and
// arr2 respectively
int i = 0, j = 0;
int n = arr1.GetLength(0),
m = arr2.GetLength(0);
// Loop through all intervals unless
// one of the interval gets exhausted
while (i < n && j < m)
{
// Left bound for intersecting segment
int l = Math.Max(arr1[i, 0], arr2[j, 0]);
// Right bound for intersecting segment
int r = Math.Min(arr1[i, 1], arr2[j, 1]);
// If segment is valid print it
if (l <= r)
Console.WriteLine("{" + l + ", " +
r + "}");
// If i-th interval's right bound is
// smaller increment i else increment j
if (arr1[i, 1] < arr2[j, 1])
i++;
else
j++;
}
}
// Driver code
public static void Main(String[] args)
{
int [,]arr1 = { { 0, 4 }, { 5, 10 },
{ 13, 20 }, { 24, 25 } };
int [,]arr2 = { { 1, 5 }, { 8, 12 },
{ 15, 24 }, { 25, 26 } };
printIntervals(arr1, arr2);
}
}
// This code is contributed by Princi Singh
Javascript
<script>
// JavaScript implementation to find
// intersecting intervals
// Function to print intersecting intervals
function printIntervals(arr1, arr2)
{
// i and j pointers for arr1 and
// arr2 respectively
var i = 0, j = 0;
var n = arr1.length, m = arr2.length;
// Loop through all intervals unless
// one of the interval gets exhausted
while (i < n && j < m)
{
// Left bound for intersecting segment
var l = Math.max(arr1[i][0], arr2[j][0]);
// Right bound for intersecting segment
var r = Math.min(arr1[i][1], arr2[j][1]);
// If segment is valid print it
if (l <= r)
document.write("{" + l + ", " +
r + "}" + "<br>");
// If i-th interval's right bound is
// smaller increment i else increment j
if (arr1[i][1] < arr2[j][1])
i++;
else
j++;
}
}
// Driver code
var arr1 = [ [ 0, 4 ], [ 5, 10 ],
[ 13, 20 ], [ 24, 25 ] ];
var arr2 = [ [ 1, 5 ], [ 8, 12 ],
[ 15, 24 ], [ 25, 26 ] ];
printIntervals(arr1, arr2);
// This code is contributed by shivanisinghss2110
</script>
{1, 4}
{5, 5}
{8, 10}
{15, 20}
{24, 24}
{25, 25}
Complejidad de tiempo: O(N + M), donde N y M son longitudes de las arrays 2-D
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por sarthak_eddy y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA