Minimice el tiempo para completar N tareas cuando se asigna la tarea realizada por cada una

Dadas N tareas y N personas que pueden trabajar en ellas. Cada tarea requiere A[i] (0 <= i <= N-1) unidades de trabajo para completar y cada persona puede hacer como máximo B[i] unidades de trabajo por día. Asigne una tarea a cada persona para que se minimice el tiempo total necesario para completar todas las tareas. Encuentre el número mínimo de días necesarios para completar todas las tareas.

Nota: Cada persona tiene que hacer exactamente una tarea y dos o más personas no pueden trabajar en la misma tarea.

Ejemplos:

Entrada: N = 3, A = {6, 3, 6}, B = {2, 6, 8}
Salida : 2
Explicación: Asigne la primera tarea a la segunda persona, la segunda tarea a la primera persona y la tercera tarea a la tercera persona.
Los días tomados por 1ra, 2da y 3ra persona serán: 2, 1, 1 

Entrada: N = 2, A = {100, 100}, B = {1, 200}
Salida: 100
Explicación: Dado que el trabajo requerido por ambas tareas es el mismo, podemos asignarlas en cualquier orden.

Enfoque: Para resolver el problema, siga la siguiente idea:

Asigne la cantidad máxima de trabajo a la persona que puede hacer el máximo de unidades de trabajo por día. Esto da como resultado el cálculo de los días mínimos necesarios para completar todas las tareas. 

Siga los pasos dados para resolver el problema:

• Ordenar ambas arrays en orden decreciente
• Iterar sobre ambas arrays simultáneamente para calcular la cantidad de días
  • Si A[i] es menor o igual que B[i], entonces solo se requiere un día para completar esta tarea
  • De lo contrario, si A[i] % B[i] no es igual a cero , se requerirá (A[i] / B[i]) + 1 días
  • De lo contrario, se requerirán días A[i] / B[i] .
• El valor máximo de los días calculados es la respuesta requerida.

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

// Java program for the above approach
 
import java.io.*;
import java.util.*;
 
class GFG {
 
    static int solve(int N, Integer[] A, Integer[] B)
    {
        // sorting A and B in decreasing order
        Arrays.sort(A, Collections.reverseOrder());
        Arrays.sort(B, Collections.reverseOrder());
 
        int res = 0;
        for (int i = 0; i < N; i++) {
            // If A[i]<=B[i] then, only one day is required
            // to complete the task
            if ((A[i] / B[i]) < 1) {
                res = Math.max(res, 1);
            }
            else {
                if ((A[i] % B[i]) != 0) {
                    res = Math.max((int)(A[i] / B[i]) + 1,
                                   res);
                }
                else {
                    res = Math.max(res, (int)(A[i] / B[i]));
                }
            }
        }
        return res;
    }
 
    public static void main(String[] args)
    {
        Integer[] A = { 1, 3, 9, 5, 3 };
        Integer[] B = { 6, 1, 5, 8, 5 };
 
        int N = A.length;
       
        // Function call
        System.out.print(solve(N, A, B));
    }
}
 
// This code is contributed by lokeshmvs21.

# Python3 program for
# the above approach
 
 
def solve(N, A, B):
 
    # Sorting A and B in decreasing order
    A.sort(reverse = True)
    B.sort(reverse = True)
    res = 0
    for i in range(0, N):
 
        # If A[i]<= B[i] then, only one day
        # is required to complete the  task
        if(A[i] / B[i] <= 1):
            res = max(res, 1)
        else:
            if(A[i] % B[i] != 0):
                res = max((A[i] // B[i]) + 1, res)
            else:
                res = max(res, A[i] // B[i])
    return res
 
 
# Driver Code
if __name__ == '__main__':
    A = [1, 3, 9, 5, 3]
    B = [6, 1, 5, 8, 5]
    N = len(A)
     
    # Function call
    print(str(solve(N, A, B)))

2

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