Dada una array 2D arr[][] que consta de N pares de enteros, la tarea es encontrar el par que cubre todos los demás pares de la array dada. Si es imposible encontrar tal par, imprima -1 .
Un par { a, b} cubrirá otro par {c, d} , si la condición (a ≤ c ≤ d ≤ b) se cumple.
Ejemplos:
Entrada: arr[][2] = {{2, 2}, {3, 3}, {3, 5}, {4, 5}, {1, 1}, {1, 5}}
Salida: 6
Explicación :
Existe un par (1, 5) que cubre todos los demás pares porque todos los demás pares se encuentran en el par {1, 5}.
Por lo tanto, la posición del par {1, 5} es 6. Entonces, la salida es 6.Entrada: arr[][] = {{1, 20}, {2, 22}, {3, 18}}
Salida: -1
Explicación:
No existe tal par que cubra todos los pares restantes.
Por lo tanto, la salida es -1
Enfoque ingenuo: el enfoque más simple es comparar cada par con todos los demás pares y verificar si algún par cubre todos los pares o no. A continuación se muestran los pasos:
- Inicialice una variable count = 0 que almacena el número de pares que se encuentran entre el par actual.
- Recorra la array de pares y, para cada par, verifique si el conteo es igual al número total de pares o no.
- Si se determina que es cierto, significa que el par puede cubrir todos los demás pares. Imprime el par.
- De lo contrario, configure el conteo = 0 y repita los pasos anteriores para el siguiente par.
- Si no existe tal par, imprima -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;
// Function to find the position of
// the pair that covers every pair
// in the array arr[][]
void position(int arr[][2], int N)
{
// Stores the index of the
// resultant pair
int pos = -1;
// To count the occurrences
int count;
// Iterate to check every pair
for (int i = 0; i < N; i++) {
// Set count to 0
count = 0;
for (int j = 0; j < N; j++) {
// Condition to checked for
// overlapping of pairs
if (arr[i][0] <= arr[j][0]
&& arr[i][1] >= arr[j][1]) {
count++;
}
}
// If that pair can cover all other
// pairs then store its position
if (count == N) {
pos = i;
}
}
// If position not found
if (pos == -1) {
cout << pos;
}
// Otherwise
else {
cout << pos + 1;
}
}
// Driver Code
int main()
{
// Given array of pairs
int arr[][2] = {{ 3, 3 }, { 1, 3 },
{ 2, 2 }, { 2, 3 },
{ 1, 2 }};
int N = sizeof(arr) / sizeof(arr[0]);
// Function Call
position(arr, N);
}
Java
// Java program for
// the above approach
import java.util.*;
class GFG{
// Function to find the position of
// the pair that covers every pair
// in the array arr[][]
static void position(int arr[][],
int N)
{
// Stores the index of the
// resultant pair
int pos = -1;
// To count the occurrences
int count;
// Iterate to check every pair
for (int i = 0; i < N; i++)
{
// Set count to 0
count = 0;
for (int j = 0; j < N; j++)
{
// Condition to checked for
// overlapping of pairs
if (arr[i][0] <= arr[j][0] &&
arr[i][1] >= arr[j][1])
{
count++;
}
}
// If that pair can cover all other
// pairs then store its position
if (count == N)
{
pos = i;
}
}
// If position not found
if (pos == -1)
{
System.out.print(pos);
}
// Otherwise
else
{
System.out.print(pos + 1);
}
}
// Driver Code
public static void main(String[] args)
{
// Given array of pairs
int arr[][] = {{3, 3}, {1, 3},
{2, 2}, {2, 3},
{1, 2}};
int N = arr.length;
// Function Call
position(arr, N);
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 program for # the above approach # Function to find the position of # the pair that covers every pair # in the array arr def position(arr, N): # Stores the index of the # resultant pair pos = -1; # To count the occurrences count = 0; # Iterate to check every pair for i in range(N): # Set count to 0 count = 0; for j in range(N): # Condition to checked for # overlapping of pairs if (arr[i][0] <= arr[j][0] and arr[i][1] >= arr[j][1]): count += 1; # If that pair can cover # all other pairs then # store its position if (count == N): pos = i; # If position not found if (pos == -1): print(pos); # Otherwise else: print(pos + 1); # Driver Code if __name__ == '__main__': # Given array of pairs arr = [[3, 3], [1, 3], [2, 2], [2, 3], [1, 2]]; N = len(arr); # Function Call position(arr, N); # This code is contributed by shikhasingrajput
C#
// C# program for
// the above approach
using System;
class GFG{
// Function to find the position of
// the pair that covers every pair
// in the array arr[][]
static void position(int[,] arr,
int N)
{
// Stores the index of the
// resultant pair
int pos = -1;
// To count the occurrences
int count;
// Iterate to check every pair
for(int i = 0; i < N; i++)
{
// Set count to 0
count = 0;
for(int j = 0; j < N; j++)
{
// Condition to checked for
// overlapping of pairs
if (arr[i, 0] <= arr[j, 0] &&
arr[i, 1] >= arr[j, 1])
{
count++;
}
}
// If that pair can cover
// all other pairs then
// store its position
if (count == N)
{
pos = i;
}
}
// If position not found
if (pos == -1)
{
Console.Write(pos);
}
// Otherwise
else
{
Console.Write(pos + 1);
}
}
// Driver Code
public static void Main()
{
// Give array of pairs
int[,] arr = {{3, 3}, {1, 3},
{2, 2}, {2, 3},
{1, 2}};
int N = arr.GetLength(0);
// Function Call
position(arr, N);
}
}
// This code is contributed by sanjoy_62
Javascript
<script>
// Javascript program for
// the above approach
// Function to find the position of
// the pair that covers every pair
// in the array arr[][]
function position(arr, N)
{
// Stores the index of the
// resultant pair
let pos = -1;
// To count the occurrences
let count;
// Iterate to check every pair
for (let i = 0; i < N; i++)
{
// Set count to 0
count = 0;
for (let j = 0; j < N; j++)
{
// Condition to checked for
// overlapping of pairs
if (arr[i][0] <= arr[j][0] &&
arr[i][1] >= arr[j][1])
{
count++;
}
}
// If that pair can cover all other
// pairs then store its position
if (count == N)
{
pos = i;
}
}
// If position not found
if (pos == -1)
{
document.write(pos);
}
// Otherwise
else
{
document.write(pos + 1);
}
}
// Driver Code
// Given array of pairs
let arr = [[3, 3], [1, 3],
[2, 2], [2, 3],
[1, 2]];
let N = arr.length;
// Function Call
position(arr, N);
</script>
Producción
2
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)
Enfoque eficiente: para optimizar el enfoque anterior, la idea es observar que la respuesta siempre es única porque siempre hay un par único que contiene tanto el valor mínimo como el máximo. A continuación se muestran los pasos:
- Iterar sobre la array de pares dada y encontrar el primer par mínimo y el segundo par máximo de todos los pares en arr[][] .
- Después de encontrar el máximo y el mínimo en el paso anterior, debe existir cualquier par con arr[i][0] = mínimo y arr[i][1] = máximo.
- Iterar a través de cada array de pares y verificar si existe un par cuyo arr[i][0] sea igual al mínimo y arr[i][1] sea igual al máximo.
- Si existe alguna posición en el paso anterior, imprima esa posición.
- De lo contrario, imprima -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;
// Function to find the position of
// the pair that covers every pair
// in the array arr[][]
void position(int arr[][2], int N)
{
// Position to store the index
int pos = -1;
// Stores the maximum second value
int right = INT_MIN;
// Stores the minimum first value
int left = INT_MAX;
// Iterate over the array of pairs
for (int i = 0; i < N; i++) {
// Update right maximum
if (arr[i][1] > right) {
right = arr[i][1];
}
// Update left minimum
if (arr[i][0] < left) {
left = arr[i][0];
}
}
// Iterate over the array of pairs
for (int i = 0; i < N; i++) {
// If any pair exists with value
// {left, right} then store it
if (arr[i][0] == left
&& arr[i][1] == right) {
pos = i + 1;
}
}
// Print the answer
cout << pos << endl;
}
// Driver Code
int main()
{
// Given array of pairs
int arr[][2] = {{ 3, 3 }, { 1, 3 },
{ 2, 2 }, { 2, 3 },
{ 1, 2 }};
int N = sizeof(arr) / sizeof(arr[0]);
// Function Call
position(arr, N);
}
Java
// Java program for the
// above approach
import java.util.*;
class GFG{
// Function to find the position
// of the pair that covers
// every pair in the array arr[][]
static void position(int arr[][],
int N)
{
// Position to store
// the index
int pos = -1;
// Stores the maximum
// second value
int right = Integer.MIN_VALUE;
// Stores the minimum
// first value
int left = Integer.MAX_VALUE;
// Iterate over the array
// of pairs
for (int i = 0; i < N; i++)
{
// Update right maximum
if (arr[i][1] > right)
{
right = arr[i][1];
}
// Update left minimum
if (arr[i][0] < left)
{
left = arr[i][0];
}
}
// Iterate over the array
// of pairs
for (int i = 0; i < N; i++)
{
// If any pair exists
// with value {left,
// right} then store it
if (arr[i][0] == left &&
arr[i][1] == right)
{
pos = i + 1;
}
}
// Print the answer
System.out.print(pos + "\n");
}
// Driver Code
public static void main(String[] args)
{
// Given array of pairs
int arr[][] = {{3, 3}, {1, 3},
{2, 2}, {2, 3},
{1, 2}};
int N = arr.length;
// Function Call
position(arr, N);
}
}
// This code is contributed by Princi Singh
Python3
# Python3 program for the above approach
import sys
# Function to find the position of
# the pair that covers every pair
# in the array arr[][]
def position(arr, N):
# Position to store the index
pos = -1
# Stores the minimum second value
right = -sys.maxsize - 1
# Stores the maximum first value
left = sys.maxsize
# Iterate over the array of pairs
for i in range(N):
# Update right maximum
if (arr[i][1] > right):
right = arr[i][1]
# Update left minimum
if (arr[i][0] < left):
left = arr[i][0]
# Iterate over the array of pairs
for i in range(N):
# If any pair exists with value
# {left, right then store it
if (arr[i][0] == left and
arr[i][1] == right):
pos = i + 1
# Print the answer
print(pos)
# Driver Code
if __name__ == '__main__':
# Given array of pairs
arr = [ [ 3, 3 ], [ 1, 3 ],
[ 2, 2 ], [ 2, 3 ],
[ 1, 2 ] ]
N = len(arr)
# Function call
position(arr, N)
# This code is contributed by mohit kumar 29
C#
// C# program for the
// above approach
using System;
class GFG{
// Function to find the position
// of the pair that covers
// every pair in the array [,]arr
static void position(int [,]arr,
int N)
{
// Position to store
// the index
int pos = -1;
// Stores the maximum
// second value
int right = int.MinValue;
// Stores the minimum
// first value
int left = int.MaxValue;
// Iterate over the array
// of pairs
for (int i = 0; i < N; i++)
{
// Update right maximum
if (arr[i, 1] > right)
{
right = arr[i, 1];
}
// Update left minimum
if (arr[i, 0] < left)
{
left = arr[i, 0];
}
}
// Iterate over the array
// of pairs
for (int i = 0; i < N; i++)
{
// If any pair exists
// with value {left,
// right} then store it
if (arr[i, 0] == left &&
arr[i, 1] == right)
{
pos = i + 1;
}
}
// Print the answer
Console.Write(pos + "\n");
}
// Driver Code
public static void Main(String[] args)
{
// Given array of pairs
int [,]arr = {{3, 3}, {1, 3},
{2, 2}, {2, 3},
{1, 2}};
int N = arr.GetLength(0);
// Function Call
position(arr, N);
}
}
// This code is contributed by shikhasingrajput
Javascript
<script>
// JavaScript program for the above approach
// Function to find the position of
// the pair that covers every pair
// in the array arr[][]
function position(arr, N){
// Position to store the index
let pos = -1
// Stores the minimum second value
let right = Number.MIN_VALUE
// Stores the maximum first value
let left = Number.MAX_VALUE
// Iterate over the array of pairs
for(let i=0;i<N;i++){
// Update right maximum
if (arr[i][1] > right)
right = arr[i][1]
// Update left minimum
if (arr[i][0] < left)
left = arr[i][0]
}
// Iterate over the array of pairs
for(let i=0;i<N;i++){
// If any pair exists with value
// {left, right then store it
if (arr[i][0] == left && arr[i][1] == right)
pos = i + 1
}
// Print the answer
document.write(pos,"</br>")
}
// Driver Code
// Given array of pairs
let arr = [ [ 3, 3 ], [ 1, 3 ], [ 2, 2 ], [ 2, 3 ], [ 1, 2 ] ]
let N = arr.length
// Function call
position(arr, N)
// This code is contributed by shinjanpatra
</script>
Producción
2
Complejidad temporal: O(N)
Espacio auxiliar: O(1)