Repartir candidatos entre dos ciudades
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
Mandar a cada uno a su oficina más barata falla cuando demasiados prefieren la misma. Piensa en cuánto cuesta mover a un candidato de A a B.
Mover al candidato i de A a B cambia el total en b menos a. Los que más ahorran volando a A deberían ser los que reciben A.
Ordena los candidatos por a menos b, del más negativo al más positivo. Manda la primera mitad a A y la segunda a B, y suma las tarifas.
- Tiempo objetivo
- O(n log n)
- Espacio objetivo
- O(n)
Restricciones
- the number of candidates is even
Solución
Imagina que todos vuelan primero a B; pasar al candidato i a A cambia entonces el total en a menos b, y exactamente la mitad de los candidatos tiene que cambiar. La forma más barata de elegirlos es tomar la mitad con los valores más pequeños de a menos b, así que la lista se ordena por esa diferencia y se parte por la mitad. Un argumento de intercambio lo confirma: cambiar cualquier candidato de A por uno de B con una diferencia menor solo podría bajar el total. El tiempo es O(n log n) por el ordenamiento y el espacio es O(n) para la copia ordenada.
def split_cities(costs):
costs = sorted(costs, key=lambda c: c[0] - c[1]) # most eager for A first
half = len(costs) // 2
return sum(a for a, _ in costs[:half]) + sum(b for _, b in costs[half:])
print(split_cities([[10, 20], [30, 200], [400, 50], [30, 20]])) # -> 110
print(split_cities([[259, 770], [448, 54], [926, 667], [184, 139], [840, 118], [577, 469]])) # -> 1859
print(split_cities([[5, 5], [7, 7]])) # -> 12¿Lo que te frena es la idea y no el código? Fundamentos del ordenamiento lo explica.