Consultas para verificar si existe algún par en una array que tenga valores como máximo iguales al par dado

Dado un vector de pares arr[] y Q consultas en forma de pares en una array Queries[] , la tarea de cada consulta es verificar si existe algún par con valores más pequeños que los del par de la consulta actual . Si se encuentra que es cierto, escriba «Sí» . De lo contrario, escriba “No” .

Ejemplos:

Entrada: arr[][] = {{3, 5}, {2, 7}, {2, 3}, {4, 9}}, Consultas[][] = {{3, 4}, {3, 2}, {4, 1}, {3, 7}}
Salida:
Sí
No
No
Sí
Explicación:
Consulta 1: el par {2, 3} existe en arr[] que tiene ambos valores menores que {3, 4}.
Consulta 2: no se encontró ningún par válido en arr[] para {3, 2}.
Consulta 3: No se encontró ningún par válido en arr[] para {4, 1}.
Consulta 4: el par {2, 7} existe en arr[] para {3, 7}.

Entrada: arr[][] = {{2, 1}, {4, 2}, {4, 4}, {7, 2}}, Consultas[][] = {{2, 1}, {1, 1}}
Salida:
Sí
No

Enfoque ingenuo: el enfoque más simple es recorrer la array Consultas [] [] y, para cada par, recorrer la array de pares dada y verificar si existe algún par cuyos valores correspondientes sean mayores o iguales que el par {p1, p2 } luego imprima “Sí” . De lo contrario, escriba “No” . 

Complejidad temporal: O(N*K)
Espacio auxiliar: O(1)

Enfoque eficiente: para optimizar el enfoque anterior, la idea es utilizar la búsqueda binaria . Siga los pasos a continuación para resolver este problema:

• Ordene la array de pares con respecto al primer elemento de los pares en orden creciente. Si existen 2 pares cuyos primeros valores son iguales, entonces los pares se organizan sobre la base del segundo elemento del par.
• Después de ordenar, recorra la array de pares y, para todos los pares que tengan el mismo primer valor, reemplace el segundo valor con el mínimo de todos los pares que tengan el mismo primer valor.
• Ahora, recorra las arrays Queries[] dadas y realice una búsqueda binaria en la array arr[] para cada par en ella.
• Si los pares obtenidos de los pasos anteriores son más pequeños que el par actual en Query[] , imprima «Sí»; de lo contrario, imprima «No» .

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function that performs binary search
// to find value less than or equal to
// first value of the pair
int binary_search(vector<pair<int, int> > vec,
                  int n, int a)
{
    int low, high, mid;
    low = 0;
    high = n - 1;
 
    // Perform binary search
    while (low < high) {
        // Find the mid
        mid = low + (high - low + 1) / 2;
 
        // Update the high
        if (vec[mid].first > a) {
            high = mid - 1;
        }
 
        // Else update low
        else if (vec[mid].first <= a) {
            low = mid;
        }
    }
 
    // Return the low index
    return low;
}
 
// Function to modify the second
// value of each pair
void modify_vec(
    vector<pair<int, int> >& v, int n)
{
    // start from index 1
    for (int i = 1; i < n; i++) {
        v[i].second
            = min(v[i].second,
                  v[i - 1].second);
    }
}
 
// Function to evaluate each query
int evaluate_query(vector<pair<int, int> > v,
                   int n, int m1,
                   int m2)
{
    // Find value less than or equal to
    // the first value of pair
    int temp = binary_search(v, n, m1);
 
    // check if we got the required
    // pair or not
    if ((v[temp].first <= m1)
        && (v[temp].second <= m2)) {
        return 1;
    }
 
    return 0;
}
 
// Function to find a pair whose values is
// less than the given pairs in query
void checkPairs(vector<pair<int, int> >& v,
                vector<pair<int, int> >& queries)
{
 
    // Find the size of the vector
    int n = v.size();
 
    // sort the vector based on
    // the first value
    sort(v.begin(), v.end());
 
    // Function Call to modify the
    // second value of each pair
    modify_vec(v, n);
 
    int k = queries.size();
 
    // Traverse each queries
    for (int i = 0; i < k; i++) {
        int m1 = queries[i].first;
        int m2 = queries[i].second;
 
        // Evaluate each query
        int result
            = evaluate_query(v, n, m1, m2);
 
        // Print the result
        if (result > 0)
            cout << "Yes\n";
        else
            cout << "No\n";
    }
}
 
// Driver Code
int main()
{
    vector<pair<int, int> > arr
        = { { 3, 5 }, { 2, 7 }, { 2, 3 }, { 4, 9 } };
 
    vector<pair<int, int> > queries
        = { { 3, 4 }, { 3, 2 }, { 4, 1 }, { 3, 7 } };
 
    // Function Call
    checkPairs(arr, queries);
 
    return 0;
}

// Java program for above approach
import java.util.*;
import java.lang.*;
class GFG{
 
  // Function that performs binary search
  // to find value less than or equal to
  // first value of the pair
  static int binary_search(int[][] vec,
                           int n, int a)
  {
    int low, high, mid;
    low = 0;
    high = n - 1;
 
    // Perform binary search
    while (low < high)
    {
 
      // Find the mid
      mid = low + (high - low + 1) / 2;
 
      // Update the high
      if (vec[mid][0] > a)
      {
        high = mid - 1;
      }
 
      // Else update low
      else if (vec[mid][1] <= a)
      {
        low = mid;
      }
    }
 
    // Return the low index
    return low;
  }
 
  // Function to modify the second
  // value of each pair
  static void modify_vec(
    int[][] v, int n)
  {
    // start from index 1
    for (int i = 1; i < n; i++)
    {
      v[i][1] =  Math.min(v[i][1],
                          v[i - 1][1]);
    }
  }
 
  // Function to evaluate each query
  static int evaluate_query(int[][] v,
                            int n, int m1,
                            int m2)
  {
 
    // Find value less than or equal to
    // the first value of pair
    int temp = binary_search(v, n, m1);
 
    // check if we got the required
    // pair or not
    if ((v[temp][0] <= m1)
        && (v[temp][1] <= m2))
    {
      return 1;
    }
 
    return 0;
  }
 
  // Function to find a pair whose values is
  // less than the given pairs in query
  static void checkPairs(int[][] v,
                         int[][] queries)
  {
 
    // Find the size of the vector
    int n = v.length;
 
    // sort the vector based on
    // the first value
    Arrays.sort(v, (a, b)->a[0]-b[0]);
 
    // Function Call to modify the
    // second value of each pair
    modify_vec(v, n);
    int k = queries.length;
 
    // Traverse each queries
    for (int i = 0; i < k; i++)
    {
      int m1 = queries[i][0];
      int m2 = queries[i][1];
 
      // Evaluate each query
      int result
        = evaluate_query(v, n, m1, m2);
 
      // Print the result
      if (result > 0)
        System.out.println("Yes");
      else
        System.out.println("No");
    }
  }
 
 
  // Driver function
  public static void main (String[] args)
  {
    int[][] arr
      = { { 3, 5 }, { 2, 7 }, { 2, 3 }, { 4, 9 } };
 
    int[][] queries
      = { { 3, 4 }, { 3, 2 }, { 4, 1 }, { 3, 7 } };
 
    // Function Call
    checkPairs(arr, queries);
  }
}
 
// This code is contributed by offbeat

# Python3 program for the above approach
 
# Function that performs binary search
# to find value less than or equal to
# first value of the pair
def binary_search(vec, n, a):
    low, high, mid = 0, 0, 0
    low = 0
    high = n - 1
 
    # Perform binary search
    while (low < high):
 
      # Find the mid
        mid = low + (high - low + 1) // 2
 
        # Update the high
        if (vec[mid][0] > a):
            high = mid - 1
         
        # Else update low
        elif vec[mid][0] <= a:
            low = mid
 
    # Return the low index
    return low
 
# Function to modify the second
# value of each pair
def modify_vec(v, n):
     
    # start from index 1
    for i in range(n):
        v[i][1] = min(v[i][1], v[i - 1][1])
 
    return v
 
# Function to evaluate each query
def evaluate_query(v, n, m1, m2):
 
    # Find value less than or equal to
    # the first value of pair
    temp = binary_search(v, n, m1)
 
    # check if we got the required
    # pair or not
    if ((v[temp][0] <= m1)
        and (v[temp][1] <= m2)):
        return 1
 
    return 0
 
# Function to find a pair whose values is
# less than the given pairs in query
def checkPairs(v, queries):
 
    # Find the size of the vector
    n = len(v)
 
    # sort the vector based on
    # the first value
    v = sorted(v)
 
    # Function Call to modify the
    # second value of each pair
    v = modify_vec(v, n)
 
    k = len(queries)
 
    # Traverse each queries
    for i in range(k):
        m1 = queries[i][0]
        m2 = queries[i][1]
 
        # Evaluate each query
        result = evaluate_query(v, n, m1, m2)
 
        # Print the result
        if (result > 0):
            print("Yes")
        else:
            print("No")
 
# Driver Code
if __name__ == '__main__':
    arr= [ [ 3, 5 ], [ 2, 7 ], [ 2, 3 ], [ 4, 9 ] ]
 
    queries = [ [ 3, 4 ], [ 3, 2 ], [ 4, 1 ], [ 3, 7 ] ]
 
    # Function Call
    checkPairs(arr, queries)
 
# This code is contributed by mohit kumar 29

<script>
// Javascript program for above approach
 
// Function that performs binary search
  // to find value less than or equal to
  // first value of the pair
function binary_search(vec,a,n)
{
    let low, high, mid;
    low = 0;
    high = n - 1;
  
    // Perform binary search
    while (low < high)
    {
  
      // Find the mid
      mid = low + Math.floor((high - low + 1) / 2);
  
      // Update the high
      if (vec[mid][0] > a)
      {
        high = mid - 1;
      }
  
      // Else update low
      else if (vec[mid][1] <= a)
      {
        low = mid;
      }
    }
  
    // Return the low index
    return low;
}
 
 // Function to modify the second
  // value of each pair
function modify_vec(v,n)
{
    // start from index 1
    for (let i = 1; i < n; i++)
    {
      v[i][1] =  Math.min(v[i][1],
                          v[i - 1][1]);
    }
}
 
// Function to evaluate each query
function evaluate_query(v,n,m1,m2)
{
    // Find value less than or equal to
    // the first value of pair
    let temp = binary_search(v, n, m1);
  
    // check if we got the required
    // pair or not
    if ((v[temp][0] <= m1)
        && (v[temp][1] <= m2))
    {
      return 1;
    }
  
    return 0;   
}
 
 // Function to find a pair whose values is
  // less than the given pairs in query
function checkPairs(v, queries)
{
    // Find the size of the vector
    let n = v.length;
  
    // sort the vector based on
    // the first value
    v.sort(function(a, b){return a[0]-b[0]});
  
    // Function Call to modify the
    // second value of each pair
    modify_vec(v, n);
    let k = queries.length;
  
    // Traverse each queries
    for (let i = 0; i < k; i++)
    {
      let m1 = queries[i][0];
      let m2 = queries[i][1];
  
      // Evaluate each query
      let result
        = evaluate_query(v, n, m1, m2);
  
      // Print the result
      if (result > 0)
        document.write("Yes<br>");
      else
        document.write("No<br>");
    }
}
 
// Driver function
let arr=[[ 3, 5 ], [ 2, 7 ], [ 2, 3 ], [ 4, 9 ]];
 
let queries=[[ 3, 4 ], [ 3, 2 ], [ 4, 1 ], [ 3, 7 ]];
 
// Function Call
checkPairs(arr, queries);
 
// This code is contributed by unknown2108
</script>

Yes
No
No
Yes

Complejidad temporal: O(Q*log N)
Espacio auxiliar: O(1)