Dada una array de pares arr[] de tamaño N , la tarea es encontrar dos pares cualesquiera (a, b) y (c, d) tales que a < c y b > d siempre se cumplan. Si existe alguno de esos pares, imprímalos. De lo contrario, imprima » NO EXISTE TAL PAR «.
Ejemplos:
Entrada: arr[] = {(3, 7), (21, 23), (4, 13), (1, 2), (7, -1)}
Salida: Los pares requeridos son (3, 7), ( 7, -1)
Explicación: (a, b) = (3, 7)
(c, d) = (7, -1)
Claramente, a < cyb > d.Entrada: arr[]={(1, 6), (-5, 4), (10, 13)}
Salida: NO EXISTE TAL PAR
Enfoque ingenuo: el enfoque más simple para resolver este problema es verificar cada par en la array si existe algún otro par que cumpla con la condición dada.
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;
// Function to find two pairs (a, b) and
// (c, d) such that a < c and b > d
void findPair(pair<int, int>* arr, int N)
{
for (int i = 0; i < N; i++) {
int a = arr[i].first, b = arr[i].second;
for (int j = i + 1; j < N; j++) {
int c = arr[j].first, d = arr[j].second;
if (a < c && b > d) {
cout << "(" << a << " " << b << "), ("
<< c << " " << d << ")\n";
return;
}
}
}
// If no such pair is found
cout << "NO SUCH PAIR EXIST\n";
}
// Driver Code
int main()
{
pair<int, int> arr[] = {
{ 3, 7 }, { 21, 23 },
{ 4, 13 }, { 1, 2 },
{ 7, -1 }
};
findPair(arr, 5);
}
Java
// Java implementation to sort the
// array of points by its distance
// from the given point
import java.util.*;
class GFG
{
static class pair
{
int first, second;
public pair(int first, int second)
{
this.first = first;
this.second = second;
}
}
// Function to find two pairs (a, b) and
// (c, d) such that a < c and b > d
static void findPair(pair arr[], int N)
{
for (int i = 0; i < N; i++)
{
int a = arr[i].first, b = arr[i].second;
for (int j = i + 1; j < N; j++)
{
int c = arr[j].first, d = arr[j].second;
if (a < c && b > d)
{
System.out.println( "(" + a + " " + b + "), ("
+ c + " " + d + ")");
return;
}
}
}
// If no such pair is found
System.out.println("NO SUCH PAIR EXIST");
}
// Driver code
public static void main(String[] args)
{
pair arr[] = {new pair( 3, 7 ), new pair( 21, 23 ),
new pair( 4, 13 ), new pair( 1, 2 ),
new pair( 7, -1 )};
findPair(arr, 5);
}
}
// This code is contributed by sanjoy_62.
Python3
# Python3 program for the above approach
# Function to find two pairs (a, b) and
# (c, d) such that a < c and b > d
def findPair(arr, N):
for i in range(N):
a, b = arr[i][0], arr[i][1]
for j in range(i + 1, N):
c, d = arr[j][0], arr[j][1]
if (a < c and b > d):
print("(", a, b, "), (", c, d, ")")
return
# If no such pair is found
print("NO SUCH PAIR EXIST")
# Driver Code
if __name__ == '__main__':
arr = [
[ 3, 7 ], [ 21, 23 ],
[ 4, 13 ], [ 1, 2 ],
[ 7, -1 ]
]
findPair(arr, 5)
# This code is contributed by mohit kumar 29
C#
// C# implementation to sort the
// array of points by its distance
// from the given point
using System;
public class GFG
{
class pair
{
public int first, second;
public pair(int first, int second)
{
this.first = first;
this.second = second;
}
}
// Function to find two pairs (a, b) and
// (c, d) such that a < c and b > d
static void findPair(pair []arr, int N)
{
for (int i = 0; i < N; i++)
{
int a = arr[i].first, b = arr[i].second;
for (int j = i + 1; j < N; j++)
{
int c = arr[j].first, d = arr[j].second;
if (a < c && b > d)
{
Console.WriteLine( "(" + a + " " + b + "), ("
+ c + " " + d + ")");
return;
}
}
}
// If no such pair is found
Console.WriteLine("NO SUCH PAIR EXIST");
}
// Driver code
public static void Main(String[] args)
{
pair []arr = {new pair( 3, 7 ), new pair( 21, 23 ),
new pair( 4, 13 ), new pair( 1, 2 ),
new pair( 7, -1 )};
findPair(arr, 5);
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript implementation to sort the
// array of points by its distance
// from the given point
class pair
{
constructor(first,second)
{
this.first=first;
this.second = second;
}
}
// Function to find two pairs (a, b) and
// (c, d) such that a < c and b > d
function findPair(arr,N)
{
for (let i = 0; i < N; i++)
{
let a = arr[i].first, b = arr[i].second;
for (let j = i + 1; j < N; j++)
{
let c = arr[j].first, d = arr[j].second;
if (a < c && b > d)
{
document.write( "(" + a + " " + b + "), ("
+ c + " " + d + ")<br>");
return;
}
}
}
// If no such pair is found
document.write("NO SUCH PAIR EXIST<br>");
}
// Driver code
let arr=[new pair( 3, 7 ), new pair( 21, 23 ),
new pair( 4, 13 ), new pair( 1, 2 ),
new pair( 7, -1 )];
findPair(arr, 5);
// This code is contributed by unknown2108
</script>
Producción:
(3 7), (7 -1)
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)
Enfoque eficiente: Para optimizar el enfoque anterior, la idea es resolver el problema:
- Ordene la array dada de acuerdo con el primer elemento de cada par .
- Ahora, la tarea se reduce a comprobar si existe algún par en arr[] donde arr[i].segundo < arr[i – 1].segundo ya que el primer elemento de cada par ya está ordenado.
- Entonces, simplemente recorra la array y verifique si existe tal par.
- Si se encuentra que es cierto, imprima el par.
- De lo contrario, imprima «NO EXISTE TAL PAR».
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;
// Function to find two pairs (a, b) and
// (c, d) such that a < c and b > d
void findPair(pair<int, int>* arr, int N)
{
// Sort the array in increasing
// order of first element of pairs
sort(arr, arr + N);
// Traverse the array
for (int i = 1; i < N; i++) {
int b = arr[i - 1].second;
int d = arr[i].second;
if (b > d) {
cout << "(" << arr[i - 1].first << " " << b
<< "), (" << arr[i].first << " " << d << ")";
return;
}
}
// If no such pair found
cout << "NO SUCH PAIR EXIST\n";
}
// Driver Code
int main()
{
pair<int, int> arr[] = {
{ 3, 7 }, { 21, 23 },
{ 4, 13 }, { 1, 2 },
{ 7, -1 }
};
findPair(arr, 5);
}
Java
// Java program for the above approach
import java.util.*;
class GFG
{
static class pair implements Comparable<pair>
{
int first, second;
public pair(int first, int second)
{
this.first = first;
this.second = second;
}
public int compareTo(pair p)
{
return this.first - p.first;
}
}
// Function to find two pairs (a, b) and
// (c, d) such that a < c and b > d
static void findpair(pair []arr, int N)
{
// Sort the array in increasing
// order of first element of pairs
Arrays.sort(arr);
// Traverse the array
for (int i = 1; i < N; i++)
{
int b = arr[i - 1].second;
int d = arr[i].second;
if (b > d)
{
System.out.print("(" + arr[i - 1].first + " " + b
+ "), (" + arr[i].first + " " + d + ")");
return;
}
}
// If no such pair found
System.out.print("NO SUCH PAIR EXIST\n");
}
// Driver Code
public static void main(String[] args)
{
pair arr[] = { new pair( 3, 7 ), new pair( 21, 23 ),
new pair( 4, 13 ), new pair( 1, 2 ),
new pair( 7, -1 ) };
findpair(arr, 5);
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 program for the above approach
# Function to find two pairs (a, b) and
# (c, d) such that a < c and b > d
def findPair(arr, N):
# Sort the array in increasing
# order of first element of pairs
arr.sort(key = lambda x: x[0])
# Traverse the array
for i in range(1, N):
b = arr[i - 1][1]
d = arr[i][1]
if (b > d):
print("(", arr[i - 1][0], b, "), (", arr[i][0], d, ")")
return
#If no such pair found
print("NO SUCH PAIR EXIST\n");
# Driver Code
arr = [
[ 3, 7 ], [ 21, 23 ],
[ 4, 13 ], [ 1, 2 ],
[ 7, -1 ]]
findPair(arr, 5)
# This code is contributed by Dharanendra L V
C#
// C# program for the above approach
using System;
public class GFG
{
class pair : IComparable<pair>
{
public int first, second;
public pair(int first, int second)
{
this.first = first;
this.second = second;
}
public int CompareTo(pair p)
{
return this.first - p.first;
}
}
// Function to find two pairs (a, b) and
// (c, d) such that a < c and b > d
static void findpair(pair []arr, int N)
{
// Sort the array in increasing
// order of first element of pairs
Array.Sort(arr);
// Traverse the array
for (int i = 1; i < N; i++)
{
int b = arr[i - 1].second;
int d = arr[i].second;
if (b > d)
{
Console.Write("(" + arr[i - 1].first + " " + b
+ "), (" + arr[i].first + " " + d + ")");
return;
}
}
// If no such pair found
Console.Write("NO SUCH PAIR EXIST\n");
}
// Driver Code
public static void Main(String[] args)
{
pair []arr = { new pair( 3, 7 ), new pair( 21, 23 ),
new pair( 4, 13 ), new pair( 1, 2 ),
new pair( 7, -1 ) };
findpair(arr, 5);
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// JavaScript program for the above approach
// Function to find two pairs (a, b) and
// (c, d) such that a < c and b > d
function findPair(arr, N)
{
// Sort the array in increasing
// order of first element of pairs
arr.sort( function(a, b) {
return (a[0] - b[0]) || (a[1] - b[1]);
});
// Traverse the array
for (let i = 1; i < N; i++) {
let b = arr[i - 1][1];
let d = arr[i][1];
if (b > d) {
console.log( "(" + arr[i - 1][0] + " " + b
+ "), (" + arr[i][0] + " " +d + ")");
return;
}
}
// If no such pair found
console.log( "NO SUCH PAIR EXIST");
}
// Driver Code
var arr = [
[ 3, 7 ], [ 21, 23 ],
[ 4, 13 ], [ 1, 2 ],
[ 7, -1 ]
]
findPair(arr, 5);
// Thiss code is contributed by ukasp.
</script>
Producción:
(4 13), (7 -1)
Complejidad de tiempo: O(N*logN)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por shekabhi1208 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA