Recuento de distintos pares posibles tales que el elemento de A es mayor que el elemento de B

Dadas dos arrays dadas A y B de igual longitud, la tarea es encontrar el número máximo de pares distintos de elementos que se pueden elegir de manera que el elemento de A sea estrictamente mayor que el elemento de B.

Ejemplos: 

Entrada: 
A[]={20, 30, 50} , B[]={25, 60, 40} 
Salida: 2 
Explicación: 
(30, 25) y (50, 40) son los dos pares posibles.

Entrada: 
A[]={20, 25, 60} , B[]={25, 60, 40} 
Salida: 1 
Explicación: 
(60, 25) o (60, 40) pueden ser el par requerido.  

Enfoque: Para resolver este problema, necesitamos adoptar el siguiente enfoque: 

• Ordenar ambas arrays.
• Recorra toda la longitud de la array A y verifique si el elemento actual en A es mayor que el elemento en B que actualmente apunta a B.
• Si es así, señale el siguiente elemento en ambas arrays. De lo contrario, muévase al siguiente elemento en A y verifique si es mayor que el elemento que actualmente apunta a B.
• El número de elementos atravesados ​​en el arreglo B después del recorrido completo del arreglo A da la respuesta requerida.

Ilustración: 
Consideremos las dos arrays siguientes: 
A[] = {30, 28, 45, 22} , B[] = {35, 25, 22, 48} 
Después de ordenar, las arrays parecen ser 
A[] = { 22, 28, 30, 45} , B[] = {22, 25, 35, 48}
Después de la primera iteración, dado que A[0] no es mayor que B[0], pasamos a A[1]. 
Después de la segunda iteración, pasamos a B[1] ya que A[1] es mayor que B[0]. 
Después de la tercera iteración, pasamos a B[2] ya que A[2] es mayor que B[1]. 
De manera similar, A[3] es mayor que B[2] y nos movemos a B[3]. 
Por tanto, el número de elementos atravesados ​​en B, es decir, 3, es la respuesta final. 
Los pares posibles son (28,22), (30,25), (45, 35). 

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

// C++ Program to count number of distinct
// pairs possible from the two arrays
// such that element selected from one array is
// always greater than the one selected from
// the other array
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the count
// of pairs
int countPairs(vector<int> A,
                    vector<int> B)
{
    int n = A.size();
     
    sort(A.begin(),A.end());
    sort(B.begin(),B.end());
     
    int ans = 0, i;
    for (int i = 0; i < n; i++) {
        if (A[i] > B[ans]) {
            ans++;
        }
    }
     
    return ans;
}
 
// Driver code
int main()
{
    vector<int> A = { 30, 28, 45, 22 };
    vector<int> B = { 35, 25, 22, 48 };
     
    cout << countPairs(A,B);
     
    return 0;
}

// Java program to count number of distinct
// pairs possible from the two arrays such
// that element selected from one array is
// always greater than the one selected from
// the other array
import java.util.*;
 
class GFG{
 
// Function to return the count
// of pairs
static int countPairs(int [] A,
                      int [] B)
{
    int n = A.length;
    int ans = 0;
     
    Arrays.sort(A);
    Arrays.sort(B);
     
    for(int i = 0; i < n; i++)
    {
       if (A[i] > B[ans])
       {
           ans++;
       }
    }
    return ans;
}
 
// Driver code
public static void main(String[] args)
{
    int [] A = { 30, 28, 45, 22 };
    int [] B = { 35, 25, 22, 48 };
     
    System.out.print(countPairs(A, B));
}
}
 
// This code is contributed by sapnasingh4991

# Python3 program to count number of distinct
# pairs possible from the two arrays
# such that element selected from one array is
# always greater than the one selected from
# the other array
 
# Function to return the count
# of pairs
def countPairs(A, B):
 
    n = len(A)
 
    A.sort()
    B.sort()
 
    ans = 0
    for i in range(n):
        if(A[i] > B[ans]):
            ans += 1
 
    return ans
 
# Driver code
if __name__ == '__main__':
    A = [30, 28, 45, 22]
    B = [35, 25, 22, 48]
 
    print(countPairs(A, B))
 
# This code is contributed by Shivam Singh

// C# program to count number of distinct
// pairs possible from the two arrays such
// that element selected from one array is
// always greater than the one selected from
// the other array
using System;
class GFG{
 
// Function to return the count
// of pairs
static int countPairs(int [] A,
                      int [] B)
{
    int n = A.Length;
    int ans = 0;
     
    Array.Sort(A);
    Array.Sort(B);
     
    for(int i = 0; i < n; i++)
    {
        if (A[i] > B[ans])
        {
            ans++;
        }
    }
    return ans;
}
 
// Driver code
public static void Main()
{
    int []A = { 30, 28, 45, 22 };
    int []B = { 35, 25, 22, 48 };
     
    Console.Write(countPairs(A, B));
}
}
 
// This code is contributed by Code_Mech

<script>
 
// Javascript program to count number of distinct
// pairs possible from the two arrays such
// that element selected from one array is
// always greater than the one selected from
// the other array
 
// Function to return the count
// of pairs
function countPairs(A, B)
{
    let n = A.length;
    let ans = 0;
       
    A.sort();
    B.sort();
       
    for(let i = 0; i < n; i++)
    {
       if (A[i] > B[ans])
       {
           ans++;
       }
    }
    return ans;
}
 
 
// Driver Code
     
    let A = [ 30, 28, 45, 22 ];
    let B = [ 35, 25, 22, 48 ];
       
    document.write(countPairs(A, B));
         
</script>

3

Complejidad de tiempo: O(n * log n)

Espacio Auxiliar: O(1)