Dada una array 2D ranges[][] de tamaño N * 2 , con cada fila representando un rango de la forma [L, R] , la tarea es encontrar dos rangos tales que el primer rango se encuentre completamente en el segundo rango e imprimir sus índices. Si no se puede obtener tal par de rangos, imprima -1. Si existen varios rangos de este tipo, imprima cualquiera de ellos.
El segmento [L1, R1] se encuentra dentro del segmento [L2, R2] si L1 ≥ L2 y R1 ≤ R2 .
Ejemplos:
Entrada: N = 5, ranges[][] = {{1, 5}, {2, 10}, {3, 10}, {2, 2}, {2, 15}}
Salida: 4 1
Explicación: Segmento [2, 2] se encuentra completamente dentro del segmento [1, 5], ya que 1 ≤ 2 y 2 ≤ 5.Entrada: N = 4, ranges[][] = {{2, 10}, {1, 9}, {1, 8}, {1, 7}}
Salida: -1
Explicación: No existe tal par de segmentos.
Enfoque ingenuo: el enfoque más simple para resolver el problema es iterar sobre la array y, para cada rango, atravesar la array restante para verificar si existe algún rango que se encuentre completamente dentro del rango actual o viceversa.
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)
Enfoque eficiente: para optimizar el enfoque anterior, la idea es clasificar la array de rangos mediante una función de comparación y verificar si algún segmento se encuentra dentro de otro segmento o no. Siga los pasos que se indican a continuación para resolver este problema:
- Ordene los segmentos en orden creciente de sus puntos de partida . En el caso de un par que tenga puntos iniciales iguales, ordene en orden decreciente de puntos finales.
- Ahora, recorra la array y mantenga el punto final máximo obtenido y compárelo con el del segmento actual.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Store ranges and their
// corresponding array indices
vector<pair<pair<int, int>, int> > tup;
// Function to find a pair of intersecting ranges
void findIntersectingRange(int N, int ranges[][2])
{
// Stores ending point
// of every range
int curr;
// Stores the maximum
// ending point obtained
int currPos;
// Iterate from 0 to N - 1
for (int i = 0; i < N; i++) {
int x, y;
// Starting point of
// the current range
x = ranges[i][0];
// End point of
// the current range
y = ranges[i][1];
// Push pairs into tup
tup.push_back({ { x, y }, i + 1 });
}
// Sort the tup vector
sort(tup.begin(), tup.end());
curr = tup[0].first.second;
currPos = tup[0].second;
// Iterate over the ranges
for (int i = 1; i < N; i++) {
int Q = tup[i - 1].first.first;
int R = tup[i].first.first;
// If starting points are equal
if (Q == R) {
if (tup[i - 1].first.second
< tup[i].first.second)
cout << tup[i - 1].second << ' '
<< tup[i].second;
else
cout << tup[i].second << ' '
<< tup[i - 1].second;
return;
}
int T = tup[i].first.second;
// Print the indices of the
// intersecting ranges
if (T <= curr) {
cout << tup[i].second
<< ' ' << currPos;
return;
}
else {
curr = T;
currPos = tup[i].second;
}
}
// If no such pair of segments exist
cout << "-1 -1";
}
// Driver Code
int main()
{
// Given N
int N = 5;
// Given 2d ranges[][] array
int ranges[][2] = {
{ 1, 5 }, { 2, 10 },
{ 3, 10 }, { 2, 2 },
{ 2, 15 }};
// Function call
findIntersectingRange(N, ranges);
}
Java
// Java program for the above approach
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
class GFG{
// Store ranges and their
// corresponding array indices
static ArrayList<int[]> tup = new ArrayList<>();
// Function to find a pair of intersecting ranges
static void findIntersectingRange(int N, int ranges[][])
{
// Stores ending point
// of every range
int curr;
// Stores the maximum
// ending point obtained
int currPos;
// Iterate from 0 to N - 1
for(int i = 0; i < N; i++)
{
int x, y;
// Starting point of
// the current range
x = ranges[i][0];
// End point of
// the current range
y = ranges[i][1];
// Push pairs into tup
int[] arr = { x, y, i + 1 };
tup.add(arr);
}
// Sort the tup vector
// sort(tup.begin(), tup.end());
Collections.sort(tup, new Comparator<int[]>()
{
public int compare(int[] a, int[] b)
{
if (a[0] == b[0])
{
if (a[1] == b[1])
{
return a[2] - b[2];
}
else
{
return a[1] - b[1];
}
}
return a[0] - b[0];
}
});
curr = tup.get(0)[1];
currPos = tup.get(0)[2];
// Iterate over the ranges
for(int i = 1; i < N; i++)
{
int Q = tup.get(i - 1)[0];
int R = tup.get(i)[0];
// If starting points are equal
if (Q == R)
{
if (tup.get(i - 1)[1] < tup.get(i)[1])
System.out.print(tup.get(i - 1)[2] + " " +
tup.get(i)[2]);
else
System.out.print(tup.get(i)[2] + " " +
tup.get(i - 1)[2]);
return;
}
int T = tup.get(i)[1];
// Print the indices of the
// intersecting ranges
if (T <= curr)
{
System.out.print(tup.get(i)[2] + " " +
currPos);
return;
}
else
{
curr = T;
currPos = tup.get(i)[2];
}
}
// If no such pair of segments exist
System.out.print("-1 -1");
}
// Driver Code
public static void main(String[] args)
{
// Given N
int N = 5;
// Given 2d ranges[][] array
int ranges[][] = { { 1, 5 }, { 2, 10 },
{ 3, 10 }, { 2, 2 },
{ 2, 15 } };
// Function call
findIntersectingRange(N, ranges);
}
}
// This code is contributed by sanjeev2552
Python3
# Python3 program for the above approach
# Store ranges and their
# corresponding array indices
# Function to find a pair of intersecting ranges
def findIntersectingRange(tup, N, ranges):
# Stores ending point
# of every range
curr = 0
# Stores the maximum
# ending point obtained
currPos = 0
# Iterate from 0 to N - 1
for i in range(N):
# Starting point of
# the current range
x = ranges[i][0]
# End point of
# the current range
y = ranges[i][1]
# Push pairs into tup
tup.append([ [ x, y ], i + 1 ])
# Sort the tup vector
tup = sorted(tup)
curr = tup[0][0][1]
currPos = tup[0][1]
# Iterate over the ranges
for i in range(1, N):
Q = tup[i - 1][0][0]
R = tup[i][0][0]
#If starting points are equal
if (Q == R):
if (tup[i - 1][0][1] < tup[i][0][1]):
print(tup[i - 1][1], tup[i][1])
else:
print(tup[i][1], tup[i - 1][1])
return
T = tup[i][0][1]
# Print the indices of the
# intersecting ranges
if (T <= curr):
print(tup[i][1], currPos)
return
else:
curr = T
currPos = tup[i][1]
# If no such pair of segments exist
print("-1 -1")
# Driver Code
if __name__ == '__main__':
# Given N
N = 5
# Given 2d ranges[][] array
ranges= [[ 1, 5 ], [ 2, 10 ],
[ 3, 10 ], [ 2, 2 ],
[ 2, 15 ]]
# Function call
findIntersectingRange([], N, ranges)
# This code is contributed by mohit kumar 29
Javascript
<script>
// JavaScript program for the above approach
// Store ranges and their
// corresponding array indices
let tup = [];
// Function to find a pair of intersecting ranges
function findIntersectingRange(N,ranges)
{
// Stores ending point
// of every range
let curr;
// Stores the maximum
// ending point obtained
let currPos;
// Iterate from 0 to N - 1
for(let i = 0; i < N; i++)
{
let x, y;
// Starting point of
// the current range
x = ranges[i][0];
// End point of
// the current range
y = ranges[i][1];
// Push pairs into tup
let arr = [ x, y, i + 1 ];
tup.push(arr);
}
// Sort the tup vector
// sort(tup.begin(), tup.end());
tup.sort(function(a,b)
{
if (a[0] == b[0])
{
if (a[1] == b[1])
{
return a[2] - b[2];
}
else
{
return a[1] - b[1];
}
}
return a[0] - b[0];
});
curr = tup[0][1];
currPos = tup[0][2];
// Iterate over the ranges
for(let i = 1; i < N; i++)
{
let Q = tup[i - 1][0];
let R = tup[i][0];
// If starting points are equal
if (Q == R)
{
if (tup[i - 1][1] < tup[i][1])
document.write(tup[i - 1][2] + " " +
tup[i][2]);
else
document.write(tup[i][2] + " " +
tup[i - 1][2]);
return;
}
let T = tup[i][1];
// Print the indices of the
// intersecting ranges
if (T <= curr)
{
document.write(tup[i][2] + " " +
currPos);
return;
}
else
{
curr = T;
currPos = tup[i][2];
}
}
// If no such pair of segments exist
document.write("-1 -1");
}
// Driver Code
let N = 5;
// Given 2d ranges[][] array
let ranges = [[ 1, 5 ], [ 2, 10 ],
[ 3, 10 ], [ 2, 2 ],
[ 2, 15 ]];
// Function call
findIntersectingRange(N, ranges);
// This code is contributed by patel2127
</script>
Producción:
4 1
Complejidad temporal: O(N LogN)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por ujjwalgoel1103 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA