Maximice el recuento de pares (i, j) de dos arrays que tengan un elemento de la primera array que no supere el de la segunda array

Dadas dos arrays arr1[] y arr2[] de longitudes N y M respectivamente, la tarea es encontrar el número máximo de pares (i, j) tales que 2 * arr1[i] ≤ arr2[j] ( 1 ≤ i ≤ N y 1 ≤ j ≤ M ).

Nota: Cualquier elemento de array puede ser parte de un solo par.

Ejemplos:

Entrada: N = 3, arr1[] = {3, 2, 1}, M = 4, arr2[] = {3, 4, 2, 1} Salida: 2 Explicación: Solo se pueden
elegir dos
pares
:

• (1, 3): Elija los elementos arr1[3] y arr2[1].
  Por lo tanto, par = (arr1[3], arr2[1]) = (1, 3). Además, 2 * arr1[3] ≤ arr2[1].
  Ahora los elementos en las posiciones 3 y 1 de arr1[] y arr2[] respectivamente, no se pueden elegir.
• (2, 2): Elija los elementos arr1[2] y arr2[2].
  Por lo tanto, par = (arr1[2], arr2[2]) = (2, 4). Además, 2*arr1[2] <= arr2[2].
  Ahora los elementos en la posición 2 de arr1[] y arr2[] no se pueden elegir.

Entrada: N = 1, arr1[] = {40}, M = 4, arr2[] = {10, 20, 30, 40}
Salida: 0
Explicación: 
No existe ningún par posible que satisfaga la condición.

Enfoque ingenuo: el enfoque más simple es ordenar primero las arrays y, para cada elemento arr1[i] , encontrar con avidez el elemento que es mayor o igual que el valor 2 * arr1[i] en la array dada arr2[] y luego elimine ese elemento de arr2[] incrementando el número total de pares requeridos en 1 . Después de recorrer toda la array arr1[] , imprima el número de pares.

Complejidad de tiempo: O(N * M), donde N y M son las longitudes de la array dada.
Espacio Auxiliar: O(N+M)

Enfoque eficiente: la idea es usar el algoritmo codicioso al encontrar un elemento en arr2[] que sea mayor o igual que el valor 2*arr1[i] donde 0<=i<=N-1 . Siga los pasos a continuación para resolver el problema:

1. Ordene la array arr1[] e inicialice una variable ans para almacenar el número máximo de pares.
2. Agregue todos los elementos de arr2[] en Max Heap .
3. Recorra la array arr1[] desde i = (N – 1) hasta 0 en orden no creciente.
4. Para cada elemento arr1[i] , elimine el elemento de observación del montón máximo hasta que 2*arr1[i] se vuelva más pequeño o igual que el elemento de observación e incremente ans en 1 si se encuentra dicho elemento.
5. Después de recorrer toda la array, imprima ans como el número máximo de pares.

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 to return the maximum
// number of required pairs
int numberOfPairs(int arr1[], int n,
                  int arr2[], int m)
{
 
    // Max Heap to add values of arar2[]
    priority_queue<int> pq;
    int i, j;
 
    // Sort the array arr1[]
    sort(arr1, arr1 + n);
 
    // Push all arr2[] into Max Heap
    for (j = 0; j < m; j++) {
        pq.push(arr2[j]);
    }
 
    // Initialize the ans
    int ans = 0;
 
    // Traverse the arr1[] in
    // decreasing order
    for (i = n - 1; i >= 0; i--) {
 
        // Remove element until a
        // required pair is found
        if (pq.top() >= 2 * arr1[i]) {
            ans++;
           
            pq.pop();
        }
    }
 
    // Return maximum number of pairs
    return ans;
}
 
// Driver Code
int main()
{
    // Given arrays
    int arr1[] = { 3, 1, 2 };
    int arr2[] = { 3, 4, 2, 1 };
 
    int N = sizeof(arr1) / sizeof(arr1[0]);
    int M = sizeof(arr2) / sizeof(arr2[0]);
 
    // Function Call
    cout << numberOfPairs(arr1, N,
                          arr2, M);
    return 0;
}

// Java program for the above approach
import java.io.*;
import java.util.*;
 
class GFG{
  
// Function to return the maximum
// number of required pairs
static int numberOfPairs(int[] arr1, int n,
                         int[] arr2, int m)
{
     
    // Max Heap to add values of arr2[]
    PriorityQueue<Integer> pQueue =
    new PriorityQueue<Integer>(
        new Comparator<Integer>()
    {
        public int compare(Integer lhs,
                           Integer rhs)
        {
            if (lhs < rhs)
            {
                return + 1;
            }
            if (lhs.equals(rhs))
            {
                return 0;
            }
            return -1;
        }
    });
     
    int i, j;
     
    // Sort the array arr1[]
    Arrays.sort(arr1);
     
    // Push all arr2[] into Max Heap
    for(j = 0; j < m; j++)
    {
        pQueue.add(arr2[j]);
    }
     
    // Initialize the ans
    int ans = 0;
     
    // Traverse the arr1[] in
    // decreasing order
    for(i = n - 1; i >= 0; i--)
    {
         
        // Remove element until a
        // required pair is found
        if (pQueue.peek() >= 2 * arr1[i])
        {
            ans++;
            pQueue.poll();
        }
    }
     
    // Return maximum number of pairs
    return ans;
}
 
// Driver Code
public static void main (String[] args)
{
     
    // Given arrays
    int[] arr1 = { 3, 1, 2 };
    int[] arr2 = { 3, 4, 2, 1 };
     
    int N = 3;
    int M = 4;
     
    // Function call
    System.out.println(numberOfPairs(arr1, N,
                                     arr2, M));
}
}
 
// This code is contributed by sallagondaavinashreddy7

# Python3 program for the above approach
 
# Function to return the maximum
# number of required pairs
def numberOfPairs(arr1, n, arr2, m):
   
    # Max Heap to add values of arr2[]
    pq = []
 
    # Sort the array arr1[]
    arr1.sort(reverse = False)
 
    # Push all arr2[] into Max Heap
    for j in range(m):
        pq.append(arr2[j])
 
    # Initialize the ans
    ans = 2
 
    # Traverse the arr1[] in
    # decreasing order
    i = n - 1
    while (i >= 0):
       
        # Remove element until a
        # required pair is found
        pq.sort(reverse = False)
         
        if (pq[0] >= 2 * arr1[i]):
            ans += 1
            print(pq[0])
            pq.remove(pq[0])
             
        i -= 1
 
    # Return maximum number of pairs
    return ans
 
# Driver Code
if __name__ == '__main__':
   
    # Given arrays
    arr1 = [ 3, 2, 1 ]
    arr2 = [ 3, 4, 2, 1 ]
 
    N = len(arr1)
    M = len(arr2)
 
    # Function Call
    print(numberOfPairs(arr1, N, arr2, M))
     
# This code is contributed by ipg2016107

<script>
 
// JavaScript program for the above approach
 
// Function to return the maximum
// number of required pairs
function numberOfPairs(arr1, n, arr2, m){
   
    // Max Heap to add values of arr2[]
    let pq = []
 
    // Sort the array arr1[]
    arr1.sort((a,b)=>a-b)
 
    // Push all arr2[] into Max Heap
    for(let j=0;j<m;j++)
        pq.push(arr2[j])
 
    // Initialize the ans
    let ans = 2
 
    // Traverse the arr1[] in
    // decreasing order
    let i = n - 1
    while (i >= 0){
       
        // Remove element until a
        // required pair is found
        pq.sort((a,b)=>a-b)
         
        if (pq[0] >= 2 * arr1[i]){
            ans += 1
            pq.shift()
        }
             
        i -= 1
    }
 
    // Return maximum number of pairs
    return ans
}
 
// Driver Code
   
// Given arrays
let arr1 = [ 3, 2, 1 ]
let arr2 = [ 3, 4, 2, 1 ]
 
let N = arr1.length
let M = arr2.length
 
// Function Call
document.write(numberOfPairs(arr1, N, arr2, M))
 
// This code is contributed by shinjanpatra
 
</script>

2

Complejidad de tiempo: O(N*log N + M*log M), donde N y M son las longitudes de la array dada.
Espacio Auxiliar: O(N+M)