Quién espera menos
- O(n log n) · Difícil
- Plan completo
- Python
- JavaScript
- listas
- ordenar
- ciclos
Enunciado
A Mateo le llegan todos los pedidos de golpe, y su cocina tiene una sola estufa: prepara un pedido a la vez, uno tras otro, sin pausas. Él decide en qué orden, y sabe que un pedido largo al principio hace esperar a todos los que vienen detrás.
Escribe una función que reciba tiempos, una lista de enteros positivos (los minutos que tarda cada pedido; puede venir vacía), y regrese un entero: la espera sumada de todos los clientes, con los pedidos en el orden que la deja más chica. Cada cliente espera desde que llegan los pedidos hasta que empiezan a preparar el suyo, así que el primero espera 0. Con [3, 1, 2], lo mejor es ir 1, 2 y 3: esperan 0, 1 y 1 + 2 = 3, y la suma es 4. Sin pedidos, o con uno solo, la respuesta es 0.
Ejemplos
El del ejemplo
[3, 1, 2] → 4
Un solo pedido
[5] → 0
Sin pedidos
[] → 0
Pedidos iguales
[4, 4, 4] → 12
Cuatro pedidos revueltos
[8, 2, 5, 1] → 12
Además de estas, el reto tiene pruebas ocultas que se revelan al enviar tu solución.
Empiezas con esto
Python
def espera_total(tiempos):
passJavaScript
function esperaTotal(tiempos) {
}Se abre en el navegador, con el editor y las pruebas. Este reto es del plan completo; los de O(1) y O(log n) son gratis.