Dados n pares (S[i], F[i]) donde para cada i, S[i]< F[i]. Se dice que dos rangos se intersecan si y solo si alguno de ellos no se encuentra completamente dentro del otro, que es solo un punto de un par que se encuentra entre el comienzo y el final del otro par. Tenemos que imprimir todos los rangos de intersección para cada par.
Nota: Todos los puntos finales que son F[i] son números enteros y también son únicos. Ninguno de los pares comienza y termina al mismo tiempo. Además, el punto final de ningún par es el mismo que el comienzo del otro.
Ejemplos:
Entrada:
n = 6, v = {{9, 12}, {2, 11}, {1, 3}, {6, 10}, {5, 7}, {4, 8}}
Salida:
{9, 12} se cruza con: {6, 10} {2, 11}
{2, 11} se cruza con: {1, 3} {9, 12}
{1, 3} se cruza con: {2, 11}
{ 6, 10} se cruza con: {5, 7} {4, 8} {9, 12}
{5, 7} se cruza con: {6, 10}
{4, 8} se cruza con: {6, 10 }
Explicación:
El primer par (9, 12) se cruza con el segundo (2, 11) y el cuarto (6, 10) par.
El segundo par (2, 11) se cruza con el tercero (1, 3) y el primero (9, 12) pares.
El tercer par (1, 3) se cruza con el segundo par (2, 11).
El cuarto par (6, 10) se cruza con el quinto (5, 7), el sexto (4, 8) y el primer par (9, 12).
El quinto par (5, 7) se cruza con el cuarto par (6, 10).
El sexto par (4, 8) se cruza con el cuarto par (6, 10).Entrada: n = 5, v = {1, 3}, {2, 4}, {5, 9}, {6, 8}, {7, 10}}
Salida:
{1, 3} se cruza con: { 2, 4}
{2, 4} se cruza con: {1, 3}
{5, 9} se cruza con: {7, 10}
{6, 8} se cruza con: {7, 10}
{7, 10 } se cruza con: {6, 8} {5, 9}
Explicación:
el primer par (1, 3) se cruza con el segundo par (2, 4).
El segundo par (2, 4) se cruza con el primer par (1, 3).
El tercer par (5, 9) se cruza con el quinto par (7, 10).
El cuarto par (6, 8) se cruza con el quinto par (7, 10).
El quinto par (7, 10) se cruza con el tercer par (5, 9) y el cuarto (6, 8).
Acercarse:
El problema mencionado anteriormente se puede resolver utilizando la clasificación. Primero, tenemos que insertar cada primer elemento del par y el segundo elemento del par en un solo vector junto con la posición de cada uno. Luego ordene todos los elementos con respecto al primer elemento del par. Después de eso, use una estructura de datos establecida para los segundos elementos del par. Luego, tenemos que iterar en el vector en el que hemos almacenado el primer y segundo elemento con sus respectivas posiciones y, si se encuentra el primer elemento, calcular todos los rangos que se cruzan con el par actual del conjunto y si el segundo elemento del se encuentra un par, simplemente borre ese segundo par del conjunto. De lo contrario, agregue el segundo elemento del par actual.
A continuación se muestra la implementación del enfoque anterior:
// CPP Program to Find all the
// intersecting pairs from a given array
#include <bits/stdc++.h>
using namespace std;
// Function that print intersecting pairs
// for each pair in the vector
void findIntersection(vector<pair<int, int> > v, int n)
{
vector<pair<int, int> > data;
vector<vector<int> > answer(n);
// Store each pair with their positions
for (int i = 0; i < n; i++) {
data.push_back(make_pair(v[i].first, i));
data.push_back(make_pair(v[i].second, i));
}
// Sort the vector with respect to
// first element in the pair
sort(data.begin(), data.end());
int curr = 0;
// set data structure for keeping
// the second element of each pair
set<pair<int, int> > s;
// Iterating data vector
for (auto it : data) {
// check if all pairs are taken
if (curr >= n)
break;
// check if current value is a second element
// then remove it from the set
if (s.count(it))
s.erase(it);
else {
// index of the current pair
int i = it.second;
// Computing the second element of current pair
int j = v[i].second;
// Iterating in the set
for (auto k : s) {
// Check if the set element
// has higher value than the current
// element's second element
if (k.first > j)
break;
int index = k.second;
answer[i].push_back(index);
answer[index].push_back(i);
curr++;
// Check if curr is equal to
// all available pairs or not
if (curr >= n)
break;
}
// Insert second element
// of current pair in the set
s.insert(make_pair(j, i));
}
}
// Printing the result
for (int i = 0; i < n; i++) {
cout << "{" << v[i].first << ", " << v[i].second << "}"
<< " is intersecting with: ";
for (int j = 0; j < answer[i].size(); j++)
cout << "{" << v[answer[i][j]].first << ", "
<< v[answer[i][j]].second << "}"
<< " ";
cout << "\n";
}
}
// Driver Code
int main()
{
// initialise the size of vector
int n = 6;
// initialise the vector
vector<pair<int, int> > v = { { 9, 12 },
{ 2, 11 },
{ 1, 3 },
{ 6, 10 },
{ 5, 7 },
{ 4, 8 } };
findIntersection(v, n);
return 0;
}
{9, 12} is intersecting with: {6, 10} {2, 11}
{2, 11} is intersecting with: {1, 3} {9, 12}
{1, 3} is intersecting with: {2, 11}
{6, 10} is intersecting with: {5, 7} {4, 8} {9, 12}
{5, 7} is intersecting with: {6, 10}
{4, 8} is intersecting with: {6, 10}
Publicación traducida automáticamente
Artículo escrito por nitinkr8991 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA