Dada una array 2D arr[][] de tamaño N , con cada fila representando intervalos de la forma {X, Y} ( indexación basada en 1 ), la tarea de encontrar un par de índices de intervalos superpuestos. Si no existe tal par, imprima -1 -1 .
Ejemplos:
Entrada: N = 5, arr[][] = {{1, 5}, {2, 10}, {3, 10}, {2, 2}, {2, 15}}
Salida: 4 1
Explicación: El el rango en la posición 4, es decir, (2, 2) se encuentra dentro del rango en la posición 1, es decir, (1, 5).Entrada: N = 4, arr[][] = {{2, 10}, {1, 9}, {1, 8}, {1, 7}}
Salida: -1 -1
Enfoque ingenuo: el enfoque más simple es verificar cada par de intervalos si uno de ellos se encuentra dentro del otro o no. Si no se encuentra dicho intervalo, imprima -1 -1 , de lo contrario, imprima el índice de los intervalos encontrados.
Complejidad de tiempo: O(N 2 ) donde N es el número entero dado.
Espacio Auxiliar: O(N)
Enfoque eficiente: la idea es ordenar el conjunto dado de intervalos en función de la parte izquierda de cada intervalo. Siga los pasos a continuación para resolver el problema:
- Primero, ordene los segmentos por su borde izquierdo en orden creciente almacenando el índice de cada intervalo.
- Luego, inicialice las variables curr y currPos con la parte izquierda del primer intervalo en la array ordenada y su índice respectivamente.
- Ahora, recorra los intervalos ordenados de i = 0 a N – 1 .
- Si las partes izquierdas de dos intervalos adyacentes cualesquiera son iguales, imprima sus índices como si uno de ellos estuviera dentro de otro.
- Si la parte derecha del intervalo actual es mayor que curr , establezca curr igual a esa parte derecha y currPos igual al índice de ese intervalo en la array original. De lo contrario, imprime el índice del intervalo actual y el índice almacenado en la variable currPos .
- Después de atravesar, si no se encuentra dicho intervalo, imprima -1 -1 .
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;
// Pair of two integers
// of the form {X, Y}
typedef pair<int, int> ii;
// Pair of pairs and integers
typedef pair<ii, int> iii;
// FUnction to find a pair of indices of
// the overlapping interval in the array
ii segment_overlapping(int N,
vector<vector<int> > arr)
{
// Store intervals {X, Y} along
// with their indices
vector<iii> tup;
// Traverse the given intervals
for (int i = 0; i < N; i++) {
int x, y;
x = arr[i][0];
y = arr[i][1];
// Store intervals and their indices
tup.push_back(iii(ii(x, y), i + 1));
}
// Sort the intervals
sort(tup.begin(), tup.end());
// Stores Y of the first interval
int curr = tup[0].first.second;
// Stores index of first interval
int currPos = tup[0].second;
// Traverse the sorted intervals
for (int i = 1; i < N; i++) {
// Stores X value of previous interval
int Q = tup[i - 1].first.first;
// Stores X value of current interval
int R = tup[i].first.first;
// If Q and R equal
if (Q == R) {
// If Y value of immediate previous
// interval is less than Y value of
// current interval
if (tup[i - 1].first.second
< tup[i].first.second) {
// Stores index of immediate
// previous interval
int X = tup[i - 1].second;
// Stores index of current
// interval
int Y = tup[i].second;
return { X, Y };
}
else {
// Stores index of current
// interval
int X = tup[i].second;
// Stores index of immediate
// previous interval
int Y = tup[i - 1].second;
return { X, Y };
}
}
// Stores Y value of current interval
int T = tup[i].first.second;
// T is less than or equal to curr
if (T <= curr)
return { tup[i].second, currPos };
else {
// Update curr
curr = T;
// Update currPos
currPos = tup[i].second;
}
}
// No answer exists
return { -1, -1 };
}
// Driver Code
int main()
{
// Given intervals
vector<vector<int> > arr = { { 1, 5 }, { 2, 10 },
{ 3, 10 }, { 2, 2 },
{ 2, 15 } };
// Size of intervals
int N = arr.size();
// Find answer
ii ans = segment_overlapping(N, arr);
// Print answer
cout << ans.first << " " << ans.second;
}
Java
// Java program for above approach
import java.util.*;
import java.lang.*;
// Pair of two integers
// of the form {X, Y}
class pair1
{
int first, second;
pair1(int first, int second)
{
this.first = first;
this.second = second;
}
}
// Pair of pairs and integers
class pair2
{
int first, second, index;
pair2(int first, int second, int index)
{
this.first = first;
this.second = second;
this.index = index;
}
}
class GFG
{
// Function to find a pair of indices of
// the overlapping interval in the array
static pair1 segment_overlapping(int N,
int[][] arr)
{
// Store intervals {X, Y} along
// with their indices
ArrayList<pair2> tup=new ArrayList<>();
// Traverse the given intervals
for (int i = 0; i < N; i++)
{
int x, y;
x = arr[i][0];
y = arr[i][1];
// Store intervals and their indices
tup.add(new pair2(x, y, i + 1));
}
// Sort the intervals
Collections.sort(tup, (a, b)->(a.first != b.first) ?
a.first - b.first:a.second - b.second);
// Stores Y of the first interval
int curr = tup.get(0).second;
// Stores index of first interval
int currPos = tup.get(0).index;
// Traverse the sorted intervals
for (int i = 1; i < N; i++)
{
// Stores X value of previous interval
int Q = tup.get(i - 1).first;
// Stores X value of current interval
int R = tup.get(i).first;
// If Q and R equal
if (Q == R)
{
// If Y value of immediate previous
// interval is less than Y value of
// current interval
if (tup.get(i - 1).second
< tup.get(i).second)
{
// Stores index of immediate
// previous interval
int X = tup.get(i - 1).index;
// Stores index of current
// interval
int Y = tup.get(i).index;
return new pair1( X, Y );
}
else {
// Stores index of current
// interval
int X = tup.get(i).index;
// Stores index of immediate
// previous interval
int Y = tup.get(i - 1).index;
return new pair1( X, Y );
}
}
// Stores Y value of current interval
int T = tup.get(i).second;
// T is less than or equal to curr
if (T <= curr)
return new pair1( tup.get(i).index, currPos );
else
{
// Update curr
curr = T;
// Update currPos
currPos = tup.get(i).index;
}
}
// No answer exists
return new pair1(-1, -1 );
}
// Driver function
public static void main (String[] args)
{
// Given intervals
int[][] arr = { { 1, 5 }, { 2, 10 },
{ 3, 10 }, { 2, 2 },
{ 2, 15 } };
// Size of intervals
int N = arr.length;
// Find answer
pair1 ans = segment_overlapping(N, arr);
// Print answer
System.out.print(ans.first+" "+ans.second);
}
}
// This code is contributed by offbeat
Python3
# Python3 program for the above approach
# FUnction to find a pair of indices of
# the overlapping interval in the array
def segment_overlapping(N, arr):
# Store intervals {X, Y} along
# with their indices
tup = []
# Traverse the given intervals
for i in range(N):
x = arr[i][0]
y = arr[i][1]
# Store intervals and their indices
tup.append([x, y, i + 1])
# Sort the intervals
tup = sorted(tup)
# Stores Y of the first interval
curr = tup[0][1]
# Stores index of first interval
currPos = tup[0][2]
# Traverse the sorted intervals
for i in range(1, N):
# Stores X value of previous interval
Q = tup[i - 1][0]
# Stores X value of current interval
R = tup[i][0]
# If Q and R equal
if (Q == R):
# If Y value of immediate previous
# interval is less than Y value of
# current interval
if (tup[i - 1][1] < tup[i][1]):
# Stores index of immediate
# previous interval
X = tup[i - 1][2]
# Stores index of current
# interval
Y = tup[i][2]
return [X, Y]
else:
# Stores index of current
# interval
X = tup[i][2]
# Stores index of immediate
# previous interval
Y = tup[i - 1][2]
return { X, Y }
# Stores Y value of current interval
T = tup[i][1]
# T is less than or equal to curr
if (T <= curr):
return [tup[i][2], currPos]
else:
# Update curr
curr = T
# Update currPos
currPos = tup[i][2]
# No answer exists
return [ -1, -1 ]
# Driver Code
if __name__ == '__main__':
# Given intervals
arr = [ [ 1, 5 ], [ 2, 10 ], [ 3, 10 ], [ 2, 2 ], [2, 15 ] ]
# Size of intervals
N = len(arr)
# Find answer
ans = segment_overlapping(N, arr)
# Print answer
print(ans[0], ans[1])
# This code is contributed by mohit kumar 29
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to find a pair of indices of
// the overlapping interval in the array
static void segment_overlapping(int N, int[,] arr)
{
// Store intervals {X, Y} along
// with their indices
List<Tuple<Tuple<int, int>,
int>> tup = new List<Tuple<Tuple<int, int>,
int>>();
// Traverse the given intervals
for(int i = 0; i < N; i++)
{
int x, y;
x = arr[i, 0];
y = arr[i, 1];
// Store intervals and their indices
tup.Add(new Tuple<Tuple<int, int>, int>(
new Tuple<int, int>(x, y), i + 1));
}
// Sort the intervals
tup.Sort();
// Stores Y of the first interval
int curr = tup[0].Item1.Item2;
// Stores index of first interval
int currPos = tup[0].Item2;
// Traverse the sorted intervals
for(int i = 1; i < N; i++)
{
// Stores X value of previous interval
int Q = tup[i - 1].Item1.Item1;
// Stores X value of current interval
int R = tup[i].Item1.Item1;
// If Q and R equal
if (Q == R)
{
// If Y value of immediate previous
// interval is less than Y value of
// current interval
if (tup[i - 1].Item1.Item2 <
tup[i].Item1.Item2)
{
// Stores index of immediate
// previous interval
int X = tup[i - 1].Item2;
// Stores index of current
// interval
int Y = tup[i].Item2;
Console.WriteLine(X + " " + Y);
return;
}
else
{
// Stores index of current
// interval
int X = tup[i].Item2;
// Stores index of immediate
// previous interval
int Y = tup[i - 1].Item2;
Console.WriteLine(X + " " + Y);
return;
}
}
// Stores Y value of current interval
int T = tup[i].Item1.Item2;
// T is less than or equal to curr
if (T <= curr)
{
Console.Write(tup[i].Item2 + " " + currPos);
return;
}
else
{
// Update curr
curr = T;
// Update currPos
currPos = tup[i].Item2;
}
}
// No answer exists
Console.Write("-1 -1");
}
// Driver code
static public void Main()
{
// Given intervals
int[,] arr = { { 1, 5 }, { 2, 10 },
{ 3, 10 }, { 2, 2 },
{ 2, 15 } };
// Size of intervals
int N = arr.Length / 2;
segment_overlapping(N, arr);
}
}
// This code is contributed by Dharanendra L V.
Javascript
<script>
// Javascript program for the above approach
// FUnction to find a pair of indices of
// the overlapping interval in the array
function segment_overlapping(N, arr)
{
// Store intervals {X, Y} along
// with their indices
var tup = [];
// Traverse the given intervals
for (var i = 0; i < N; i++) {
var x, y;
x = arr[i][0];
y = arr[i][1];
// Store intervals and their indices
tup.push([[x, y], i + 1]);
}
// Sort the intervals
tup.sort((a,b) =>
{
if(a[0][0] == b[0][0])
{
return a[0][1] - b[0][1];
}
var tmp = (a[0][0] - b[0][0]);
console.log(tmp);
return (a[0][0] - b[0][0])
});
// Stores Y of the first interval
var curr = tup[0][0][1];
// Stores index of first interval
var currPos = tup[0][1];
// Traverse the sorted intervals
for (var i = 1; i < N; i++) {
// Stores X value of previous interval
var Q = tup[i - 1][0][0];
// Stores X value of current interval
var R = tup[i][0][0];
// If Q and R equal
if (Q == R) {
// If Y value of immediate previous
// interval is less than Y value of
// current interval
if (tup[i - 1][0][1]
< tup[i][0][1]) {
// Stores index of immediate
// previous interval
var X = tup[i - 1][1];
// Stores index of current
// interval
var Y = tup[i][1];
return [X, Y];
}
else {
// Stores index of current
// interval
var X = tup[i][1];
// Stores index of immediate
// previous interval
var Y = tup[i - 1][1];
return [X, Y];
}
}
// Stores Y value of current interval
var T = tup[i][0][1];
// T is less than or equal to curr
if (T <= curr)
return [tup[i][1], currPos];
else {
// Update curr
curr = T;
// Update currPos
currPos = tup[i][1];
}
}
// No answer exists
return [-1, -1];
}
// Driver Code
// Given intervals
var arr = [ [ 1, 5 ], [ 2, 10 ],
[ 3, 10 ], [ 2, 2 ],
[ 2, 15 ] ];
// Size of intervals
var N = arr.length;
// Find answer
var ans = segment_overlapping(N, arr);
// Print answer
document.write( ans[0] + " " + ans[1]);
// This code is contributed by importantly.
</script>
Producción:
4 1
Complejidad de tiempo: O(N * log(N))
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