Proporcionaré una solución inspirada en la clasificación de burbujas (en realidad NO hay clasificación involucrada).
Para sacarlo del camino: la solución de fuerza bruta es obviamente inviable ya que nos deja con O (n!) De diferentes combinaciones para verificar.
La intuición detrás de esta solución es que queremos que los pilotos con el mayor Delta (DS) entre su salario de piloto (PS) y el de asistente (AS) sean los asistentes. DS (i) = Salario piloto – Salario auxiliar del piloto “i”.
- Cómo escribir mi propio algoritmo de cifrado / descifrado
- ¿Por qué los conjuntos en Python tienen una complejidad algorítmica de O (1)?
- Cómo validar un algoritmo de stock
- Cómo encontrar la tasa de ganancia más efectiva con la menor cantidad de coincidencias posible (algoritmo)
- ¿Cuál es el algoritmo utilizado por Diffbot para extraer datos web?
1. Por lo tanto, el paso es calcular para cada Piloto “i” su DS (i).
* Sin las restricciones de edad, la solución es simplemente encontrar los N / 2 Pilots con el DS (Pilot) más alto y asignarlos como asistentes.
2. Establecemos DS (0) = DS (N) = 0 ya que los más jóvenes y mayores ya tienen sus roles establecidos por la restricción de edad.
3. Ahora imagine que la matriz DS representa un conjunto de alturas.
(Similar a la representación en esta pregunta: si desea un trabajo en Twitter, prepárese para responder esta pregunta desconcertante sobre los charcos de lluvia) Nuestro objetivo es eliminar los picos. – Tome el piloto con el más alto en su vecindario DS (piloto) para ser el asistente.
El algoritmo:
1. Escaneamos desde el más antiguo al piloto y lo emparejamos con el piloto más cercano con el DS más alto (piloto)
– representará un Pico (El piloto antes y después de él tiene un DS más bajo).
2. Eliminamos estos dos pilotos de la lista de DS.
3. Establezca el DS del piloto más antiguo en 0 y repita desde 1. con el “nuevo” piloto más antiguo.
* DS debe representarse con una lista doblemente vinculada para una fácil eliminación y un escaneo más simple, ya que no desea volver a mirar a los pilotos asignados.
4. se detiene cuando le quedan dos pilotos en la lista.
Complejidad:
En cada iteración, en el peor de los casos, está escaneando a todos los pilotos de la lista restante, esta serie converge a ~ (n ^ 2) / 4 (eliminamos dos pilotos en cada iteración, no uno) Por lo tanto, es O (n ^ 2). (Orden descendente de DS – el más joven tiene el DS más alto – Gerentes de contratación sabios)
El mejor escenario es O (n). (orden ascendente de DS el más antiguo tiene el DS más alto).
La prueba de la optimización es bastante fácil pero aún demasiado larga (¿y no interesante?) Para esta publicación.
