Número máximo de elementos de una array B[] que están presentes en rangos [A[i] + K, A[i] – K]

Dadas dos arrays A[] de tamaño N y B[] de tamaño M y un número entero K , la tarea es seleccionar como máximo un elemento de la array B[] para cada elemento A[i] tal que el elemento se encuentre en el rango [A[i] – K, A[i] + K] (para 0 <= i <= N – 1 ) . Imprime el número máximo de elementos que se pueden seleccionar de la array B[]. 

Ejemplos:

Entrada: N = 4, A[] = {60, 45, 80, 60}, M = 3, B[] = {30, 60, 75}, K= 5 
Salida: 2
Explicación:
B[0] (= 30): No presente en ninguno de los rangos [A[i] + K, A[i] – K].
B[1] (= 60):B[1] se encuentra en el rango [A[0] – K, A[0] + K], es decir, [55, 65]. 
B[2] (= 75): B[2] se encuentra en el rango [A[2] – K, A[2] + K], es decir, [75, 85].

Entrada: N = 3 A[] = {10, 20, 30}, M = 3, B[] = {5, 10, 15}, K = 10
Salida: 2

Enfoque ingenuo: el enfoque más simple para resolver el problema es atravesar la array A[] , buscar linealmente en la array B[] y marcar como visitado si se selecciona el valor de la array B[] . Finalmente, imprima el número máximo de elementos de la array B[] que se pueden seleccionar.

Complejidad temporal: O(N * M)
Espacio auxiliar: O(M)

Enfoque eficiente: ordene las arrays A[] y B[] e intente asignar el elemento de B[] que está en un rango [A[i] – K, A[i] + K]. Siga los pasos a continuación para resolver el problema:

• Ordene las arrays A[] y B[].
• Inicialice una variable, digamos j como 0, para realizar un seguimiento en la array B[] y cuente como 0 para almacenar la respuesta.
• Iterar en un rango [0, N – 1] y realizar los siguientes pasos:
  • Iterar en un bucle while hasta que j < M y B[j]< A[i] – K, luego aumentar el valor de j en 1.
  • Si el valor de j es menor que M y B[j] es mayor que igual a A[i] – K y B[j] es menor que igual a A[i] + K , entonces aumente el valor de count y j en 1.
• Después de completar los pasos anteriores, imprima el valor de cuenta como el valor final de la respuesta.

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 count the maximum number of
// elements that can be selected from array
// B[] lying in the range [A[i] - K, A[i] + K]
int selectMaximumEle(int n, int m, int k,
                     int A[], int B[])
{
    // Sort both arrays
    sort(A, A + n);
    sort(B, B + m);
 
    int j = 0, count = 0;
 
    // Iterate in the range[0, N-1]
    for (int i = 0; i < n; i++) {
         
        // Increase the value of j till
        // B[j] is smaller than A[i]
        while (j < m && B[j] < A[i] - k) {
            j++;
        }
 
        // Increasing count variable when B[j]
        // lies in the range [A[i]-K, A[i]+K]
        if (j < m && B[j] >= A[i] - k
            && B[j] <= A[i] + k) {
           
            count++;
            j++;
        }
    }
     
    // Finally, return the answer
    return count;
}
 
// Driver Code
int main()
{
    // Given Input
    int N = 3, M = 3, K = 10;
    int A[] = { 10, 20, 30 };
    int B[] = { 5, 10, 15 };
     
    // Function Call
    cout << selectMaximumEle(N, M, K, A, B) << endl;
    return 0;
}

// Java program for the above approach
import java.io.*;
import java.util.Arrays;
 
class GFG
{
   
    // Function to count the maximum number of
    // elements that can be selected from array
    // B[] lying in the range [A[i] - K, A[i] + K]
    static int selectMaximumEle(int n, int m, int k,
                                int A[], int B[])
    {
        // Sort both arrays
        Arrays.sort(A);
        Arrays.sort(B);
 
        int j = 0, count = 0;
 
        // Iterate in the range[0, N-1]
        for (int i = 0; i < n; i++) {
 
            // Increase the value of j till
            // B[j] is smaller than A[i]
            while (j < m && B[j] < A[i] - k) {
                j++;
            }
 
            // Increasing count variable when B[j]
            // lies in the range [A[i]-K, A[i]+K]
            if (j < m && B[j] >= A[i] - k
                && B[j] <= A[i] + k) {
 
                count++;
                j++;
            }
        }
 
        // Finally, return the answer
        return count;
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        // Given Input
        int N = 3, M = 3, K = 10;
        int A[] = { 10, 20, 30 };
        int B[] = { 5, 10, 15 };
 
        // Function Call
        System.out.println(selectMaximumEle(N, M, K, A, B));
    }
}
 
// This code is contributed by Potta Lokesh

# Python3 program for the above approach
 
# Function to count the maximum number of
# elements that can be selected from array
# B[] lying in the range [A[i] - K, A[i] + K]
def selectMaximumEle(n, m, k, A, B):
     
    # Sort both arrays
    A.sort()
    B.sort()
 
    j = 0
    count = 0
 
    # Iterate in the range[0, N-1]
    for i in range(n):
 
        # Increase the value of j till
        # B[j] is smaller than A[i]
        while (j < m and B[j] < A[i] - k):
            j += 1
 
        # Increasing count variable when B[j]
        # lies in the range [A[i]-K, A[i]+K]
        if (j < m and B[j] >= A[i] - k
                and B[j] <= A[i] + k):
 
            count += 1
            j += 1
 
    # Finally, return the answer
    return count
 
# Driver Code
 
# Given Input
N = 3
M = 3
K = 10
A = [ 10, 20, 30 ]
B = [ 5, 10, 15 ]
 
# Function Call
print(selectMaximumEle(N, M, K, A, B))
 
# This code is contributed by gfgking

// C# program for the above approach
using System;
 
class GFG{
     
// Function to count the maximum number of
// elements that can be selected from array
// B[] lying in the range [A[i] - K, A[i] + K]
static int selectMaximumEle(int n, int m, int k,
                            int[] A, int[] B)
{
     
    // Sort both arrays
    Array.Sort(A);
    Array.Sort(B);
 
    int j = 0, count = 0;
 
    // Iterate in the range[0, N-1]
    for(int i = 0; i < n; i++)
    {
         
        // Increase the value of j till
        // B[j] is smaller than A[i]
        while (j < m && B[j] < A[i] - k)
        {
            j++;
        }
 
        // Increasing count variable when B[j]
        // lies in the range [A[i]-K, A[i]+K]
        if (j < m && B[j] >= A[i] - k &&
                     B[j] <= A[i] + k)
        {
            count++;
            j++;
        }
    }
 
    // Finally, return the answer
    return count;
}
 
// Driver code
public static void Main()
{
     
    // Given Input
    int N = 3, M = 3, K = 10;
    int[] A = { 10, 20, 30 };
    int[] B = { 5, 10, 15 };
 
    // Function Call
    Console.WriteLine(selectMaximumEle(N, M, K, A, B));
}
}
 
// This code is contributed by avijitmondal1998

<script>
    // Javascript program for the above approach
 
// Function to count the maximum number of
// elements that can be selected from array
// B[] lying in the range [A[i] - K, A[i] + K]
function selectMaximumEle(n, m, k, A, B) {
    // Sort both arrays
    A.sort((a, b) => a - b);
    B.sort((a, b) => a - b);
 
 
    let j = 0, count = 0;
 
    // Iterate in the range[0, N-1]
    for (let i = 0; i < n; i++) {
 
        // Increase the value of j till
        // B[j] is smaller than A[i]
        while (j < m && B[j] < A[i] - k) {
            j++;
        }
 
        // Increasing count variable when B[j]
        // lies in the range [A[i]-K, A[i]+K]
        if (j < m && B[j] >= A[i] - k
            && B[j] <= A[i] + k) {
 
            count++;
            j++;
        }
    }
 
    // Finally, return the answer
    return count;
}
 
// Driver Code
 
// Given Input
let N = 3, M = 3, K = 10;
let A = [10, 20, 30];
let B = [5, 10, 15];
 
// Function Call
document.write(selectMaximumEle(N, M, K, A, B) + "<br>");
 
// This code is contributed by _saurabh_jaiswal.
</script>

2

Complejidad de tiempo: O(N*log(N))
Espacio auxiliar: O(N)