Saltar al contenido

Minimice el tiempo para completar N tareas cuando se le asigne la tarea de cada

Ver discusión

Mejorar artículo

Guardar artículo

me gusta el articulo

Dado norte tareas y norte gente que pueda trabajar en ello. Cada tarea requiere: A[i] (0 <= i <= N-1) unidades de trabajo a realizar que cada persona puede realizar al máximo B[i] unidades de trabajo por día. Asigne una tarea a cada persona para que se minimice el tiempo total que lleva completar todas las tareas. Encuentre el número mínimo de días que toma completar todas las tareas.

Observación: Todo el mundo tiene que hacer exactamente una tarea y dos o más personas no pueden trabajar en la misma tarea.

Ejemplos:

Aporte: 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 registrados por la 1ª, 2ª y 3ª persona son: 2, 1, 1

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

Acercarse: Siga la siguiente idea para resolver el problema:

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

Siga los pasos dados para resolver el problema:

  • Ordenar ambas matrices en menguante ordenar
  • Repita ambas matrices al mismo tiempo para calcular la cantidad de días.
    • si A[i] es menor o igual que B[i]entonces solo se necesita un día para completar esta tarea
    • otro que A[i] % B[i] no es igual a cero (A[i] / B[i]) + 1 se requieren dias
    • De lo contrario, A[i] / B[i] se necesitarán días.
  • El valor máximo de los días calculados es la respuesta requerida.

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

Python3

 

 

def solve(N, A, B):

 

    

    A.sort(reverse = True)

    B.sort(reverse = True)

    res = 0

    for i in range(0, N):

 

        

        

        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

 

 

if __name__ == '__main__':

    A = [1, 3, 9, 5, 3]

    B = [6, 1, 5, 8, 5]

    N = len(A)

     

    

    print(str(solve(N, A, B)))

Complejidad del tiempo: O(N * registro N)
cuarto auxiliar: O(1)