Contar formas de distribuir exactamente una moneda a cada trabajador

Dadas dos arrays monedas[] y salarios[] donde monedas[i] representa el valor de la i ^-ésima moneda y salarios[j] representa el valor mínimo de la moneda que aceptará el j ^{-ésimo trabajador.} La tarea es calcular el número de formas de distribuir exactamente una moneda a cada trabajador. Como la respuesta puede ser grande, imprímela módulo 10 ⁹ + 7 .
Ejemplos:

Entrada: monedas[] = {1, 2, 3}, salarios[] = {1, 2} 
Salida: 4 
Explicación: 
Si la moneda con valor 1 no se usa, entonces las dos monedas restantes son aceptables para ambos trabajadores, contribuyendo dos formas posibles de pagar a los trabajadores. 
Si se usa la moneda con valor 1, solo se puede usar para el primer trabajador. Luego, cualquiera de las monedas restantes se puede usar para pagar al segundo trabajador. Esto también contribuye a dos formas posibles. 
Por lo tanto, las cuatro formas de pagar a los dos trabajadores son [2, 3], [3, 2], [1, 2], [1, 3].
Entrada: monedas[] = {1, 2}, salarios[] = {2} 
Salida: 1

Planteamiento: La idea es utilizar la técnica Sorting y Two Pointers para resolver el problema. Siga los pasos a continuación para resolver el problema:

• Ordenar los salarios en orden descendente.
• Sea f(i) el número de monedas utilizadas para pagar al i ^-ésimo trabajador en ausencia de otros trabajadores. Dado que la array de salario [] está ordenada, el primer trabajador exige el salario más alto y el último trabajador exige el salario más bajo. Por lo tanto, el resultado es:

• Para la función f(i) , i es igual al número de monedas que están disponibles para pagar al trabajador actual, suponiendo que se haya pagado a todos los trabajadores anteriores.
• Como los trabajadores se clasifican en orden no creciente de salarios, se garantiza que cualquier moneda utilizada para pagar a un antiguo trabajador se podrá utilizar para pagar al trabajador actual. Entonces, el número de monedas que se pueden usar para pagar al trabajador actual siempre será igual a f(i) − i , independientemente de las elecciones anteriores realizadas.
• Para calcular f(i) de manera eficiente, use dos punteros para rastrear la cantidad de monedas que son válidas actualmente.
• Imprima el recuento total de vías después de todos los pasos anteriores.

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

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
const int MOD = 1000000007;
 
// Function to find number of way to
// distribute coins giving exactly one
// coin to each person
int solve(vector<int>& values,
          vector<int>& salary)
{
    long long ret = 1;
    int amt = 0;
 
    // Sort the given arrays
    sort(values.begin(), values.end());
    sort(salary.begin(), salary.end());
 
    // Start from bigger salary
    while (salary.size()) {
        while (values.size()
               && values.back()
                      >= salary.back()) {
 
            // Increment the amount
            amt++;
            values.pop_back();
        }
        if (amt == 0)
            return 0;
 
        // Reduce amount of valid
        // coins by one each time
        ret *= amt--;
        ret %= MOD;
        salary.pop_back();
    }
 
    // Return the result
    return ret;
}
 
// Driver code
int main()
{
    // Given two arrays
    vector<int> values{ 1, 2 }, salary{ 2 };
 
    // Function Call
    cout << solve(values, salary);
 
    return 0;
}

// Java program for
// the above approach
import java.util.*;
class GFG{
 
static int MOD = 1000000007;
 
// Function to find number of way to
// distribute coins giving exactly one
// coin to each person
static int solve(Vector<Integer> values,
                 Vector<Integer> salary)
{
  int ret = 1;
  int amt = 0;
 
  // Sort the given arrays
  Collections.sort(values);
  Collections.sort(salary);
 
  // Start from bigger salary
  while (salary.size() > 0)
  {
    while (values.size() > 0 &&
           values.get(values.size() - 1) >=
           salary.get(salary.size() - 1))
    {
      // Increment the amount
      amt++;
      values.remove(values.size() - 1);
    }
     
    if (amt == 0)
      return 0;
 
    // Reduce amount of valid
    // coins by one each time
    ret *= amt--;
    ret %= MOD;
    salary.remove(salary.size() - 1);
  }
 
  // Return the result
  return ret;
}
 
// Driver code
public static void main(String[] args)
{
  // Given two arrays
  Vector<Integer> values = new Vector<Integer>();
  values.add(1);
  values.add(2);
  Vector<Integer> salary = new Vector<Integer>();
  salary.add(2);
   
  // Function Call
  System.out.print(solve(values, salary));
}
}
 
// This code is contributed by Princi Singh

# Python3 program for the above approach
MOD = 1000000007
 
# Function to find number of way to
# distribute coins giving exactly one
# coin to each person
def solve(values, salary):
     
    ret = 1
    amt = 0
 
    # Sort the given arrays
    values = sorted(values)
    salary = sorted(salary)
 
    # Start from bigger salary
    while (len(salary) > 0):
        while ((len(values) and
                values[-1] >= salary[-1])):
 
            # Increment the amount
            amt += 1
            del values[-1]
 
        if (amt == 0):
            return 0
 
        # Reduce amount of valid
        # coins by one each time
        ret *= amt
        amt -= 1
        ret %= MOD
        del salary[-1]
 
    # Return the result
    return ret
 
# Driver code
if __name__ == '__main__':
     
    # Given two arrays
    values = [ 1, 2 ]
    salary = [2]
 
    # Function call
    print(solve(values, salary))
 
# This code is contributed by mohit kumar 29

// C# program for
// the above approach
using System;
using System.Collections;
class GFG{
  
static int MOD = 1000000007;
  
// Function to find number of way to
// distribute coins giving exactly one
// coin to each person
static int solve(ArrayList values,
                 ArrayList salary)
{
  int ret = 1;
  int amt = 0;
  
  // Sort the given arrays
  values.Sort();
  salary.Sort();
  
  // Start from bigger salary
  while (salary.Count > 0)
  {
    while (values.Count > 0 &&
           (int)values[values.Count - 1] >=
           (int)salary[salary.Count - 1])
    {
      // Increment the amount
      amt++;
      values.RemoveAt(values.Count - 1);
    }
      
    if (amt == 0)
      return 0;
  
    // Reduce amount of valid
    // coins by one each time
    ret *= amt--;
    ret %= MOD;
    salary.RemoveAt(salary.Count - 1);
  }
  
  // Return the result
  return ret;
}
  
// Driver code
public static void Main(string[] args)
{
  // Given two arrays
  ArrayList values = new ArrayList();
  values.Add(1);
  values.Add(2);
  ArrayList salary = new ArrayList();
  salary.Add(2);
 
  // Function Call
  Console.Write(solve(values, salary));
}
}
 
// This code is contributed by Rutvik_56

<script>
 
// Javascript program for the above approach
var MOD = 1000000007;
 
// Function to find number of way to
// distribute coins giving exactly one
// coin to each person
function solve(values, salary)
{
    var ret = 1;
    var amt = 0;
 
    // Sort the given arrays
    values.sort((a,b)=>a-b);
    salary.sort((a,b)=>a-b);
 
    // Start from bigger salary
    while (salary.length) {
        while (values.length
               && values[values.length-1]
                      >= salary[salary.length-1]) {
 
            // Increment the amount
            amt++;
            values.pop();
        }
        if (amt == 0)
            return 0;
 
        // Reduce amount of valid
        // coins by one each time
        ret *= amt--;
        ret %= MOD;
        salary.pop();
    }
 
    // Return the result
    return ret;
}
 
// Driver code
// Given two arrays
var values = [1, 2 ], salary = [2];
 
// Function Call
document.write( solve(values, salary));
 
// This code is contributed by itsok.
</script>

1

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