Saltar al contenido

Repartir candidatos entre dos ciudades

Fácil#greedy#sort-by-difference~20 min

La misión

Problema

Una empresa va a llevar en avión a un número par de candidatos a entrevistas presenciales, y exactamente la mitad debe ir a la oficina A y la otra mitad a la oficina B. costs[i] = [a, b] da la tarifa del candidato i a cada oficina. Devuelve la menor tarifa total que envía exactamente a la mitad de los candidatos a cada oficina.

Ejemplos

Input:  costs = [[10, 20], [30, 200], [400, 50], [30, 20]]
Output: 110
Por qué: los dos primeros van a A por 10 + 30 y los dos últimos a B por 50 + 20
Input:  costs = [[259, 770], [448, 54], [926, 667], [184, 139], [840, 118], [577, 469]]
Output: 1859
Input:  costs = [[5, 5], [7, 7]]
Output: 12
Por qué: caso límite: las dos oficinas cuestan lo mismo, así que cualquier reparto en mitades es óptimo

Pistas

0 / 3

Tiempo objetivo
O(n log n)
Espacio objetivo
O(n)

Restricciones

  • the number of candidates is even

¿Lo que te frena es la idea y no el código? Fundamentos del ordenamiento lo explica.

Python 3Ctrl+Enter ejecuta
Caso de prueba propio