Maximizar el recuento de personas que reciben un chocolate

Dadas dos arrays A[] , que consisten en N enteros, y B[] , que consisten en valores de sabor de M chocolates y un entero X , la tarea es encontrar el número máximo de personas que pueden recibir un chocolate con la condición de que uno persona puede tener solo un chocolate y con valor de sabor en el rango [A[i] – X, A[i] + X] . 
Nota: Una vez que se le da un chocolate a una persona, no se le puede dar a ninguna otra persona.

Ejemplos:

Entrada: A[] = {90, 49, 20, 39, 60}, B[] = {14, 24, 82}, X = 15
Salida: 3
Explicación: 
la primera persona puede elegir el tercer chocolate como el valor del El tercer chocolate ( = 82 ) se encuentra en el rango [75 ( = 90 – 15 ), 105 ( = 90 + 15)]. 
La segunda persona no puede elegir ningún chocolate porque no hay chocolate con un valor en el rango [34 ( = 49 – 15 ), 64 ( = 49 + 15). 
La tercera persona puede elegir el primer chocolate ya que el valor del primer chocolate se encuentra en el rango [5 (= 20 – 15), 35 (= 20 – 15)]. 
La cuarta persona puede elegir el segundo chocolate porque el valor del segundo chocolate se encuentra en el rango [24 (= 39 – 15) y 54 (= 39 – 15)]. 
La quinta persona no puede elegir ningún chocolate porque no hay chocolate con un valor en el rango [45 (= 60 – 15), 75 (= 60 – 15)]. 
Por lo tanto, el número total de personas que reciben un chocolate es 3, que es el máximo posible.

Entrada: A[] = {2, 4, 6, 40, 50}, B[] = {38, 36}, X=13
Salida: 2

Enfoque: este problema se puede resolver usando la técnica codiciosa/a> y la búsqueda . La observación clave aquí es que para cualquier i ^-ésima persona , asigne el chocolate con el menor valor posible que se encuentre en el rango, si es posible. De lo contrario, excluya a esa persona del resultado. Siga los pasos a continuación:

• Ordene las arrays dadas A[] y B[] en orden no decreciente.
• Inicialice un conjunto múltiple para almacenar los elementos de la array B[] .
• Inicialice una variable count = 0 para almacenar el recuento de personas que reciben un chocolate.
• Recorra la array A[] y encuentre el valor de chocolate más pequeño posible que se pueda asignar a cada i ^-ésima persona mediante la búsqueda binaria o lower_bound() . Compruebe si ese valor se encuentra en el rango [a _i – X, a _i + X] o no.
• Si se determina que es cierto, incremente el conteo y elimine el valor de este chocolate del conjunto múltiple .
• Después de completar los pasos anteriores, imprima el valor de conteo como resultado.

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 persons receiving a chocolate
int countMaxPersons(int* A, int n, int* B,
                    int m, int x)
{
 
    // Initialize count as 0
    int count = 0;
 
    // Sort the given arrays
    sort(A, A + n);
    sort(B, B + m);
 
    // Initialize a multiset
    multiset<int> s;
 
    // Insert B[] array values into
    // the multiset
    for (int i = 0; i < m; i++)
        s.insert(B[i]);
 
    // Traverse elements in array A[]
    for (int i = 0; i < n; i++) {
        int val = A[i] - x;
 
        // Search for the lowest value in B[]
        auto it = s.lower_bound(val);
 
        // If found, increment count,
        // and delete from set
        if (it != s.end()
            && *it <= A[i] + x) {
            count++;
            s.erase(it);
        }
    }
 
    // Return the number of people
    return count;
}
 
// Driver Code
int main()
{
    int A[] = { 90, 49, 20, 39, 49 };
    int B[] = { 14, 24, 82 };
    int X = 15;
    int N = sizeof(A) / sizeof(A[0]);
    int M = sizeof(B) / sizeof(B[0]);
 
    // Function Call
    cout << countMaxPersons(A, N, B, M, X);
}

# Python3 program for the above approach
from bisect import bisect_left
 
# Function to count the maximum number
# of persons receiving a chocolate
def countMaxPersons(A, n, B, m, x):
 
    # Initialize count as 0
    count = 0
 
    # Sort the given arrays
    A = sorted(A)
    B = sorted(B)
 
    # Initialize a multiset
    s = []
 
    # Insert B[] array values into
    # the multiset
    for i in range(m):
        s.append(B[i])
 
    # Traverse elements in array A[]
    for i in range(n):
        val = A[i] - x
 
        # Search for the lowest value in B[]
        it = bisect_left(s,val)
 
        # If found, increment count,
        # and delete from set
        if (it != len(s) and it <= A[i] + x):
            count += 1
            del s[it]
 
    # Return the number of people
    return count
 
# Driver Code
if __name__ == '__main__':
 
    A = [90, 49, 20, 39, 49]
    B = [14, 24, 82]
    X = 15
    N = len(A)
    M = len(B)
 
    # Function Call
    print(countMaxPersons(A, N, B, M, X))
 
    # This code is contributed by mohit kumar 29

3

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