Car Fleet
Los autos circulan por una carretera de un solo carril hacia la milla target. El auto i comienza en la milla position[i] y circula a speed[i] millas por hora. Ningún auto puede adelantar a otro: un auto que alcanza a uno más lento se queda justo detrás de él y, a partir de ese momento, ambos avanzan juntos a la velocidad más lenta como una sola flota.
Un solo auto también constituye una flota, y un auto que alcanza a una flota justo en el destino se une a ella. Devuelve la cantidad de flotas que llegan al destino.
Función
- targetinteger
- la milla hacia la que se dirigen todos los coches
- positioninteger-array
- la milla inicial de cada automóvil
- speedinteger-array
- la velocidad de cada automóvil, en millas por hora
- Devuelveinteger
- el número de flotas que llegan al destino
Restricciones
n == position.length == speed.length1 ≤ n ≤ 1041 ≤ target ≤ 1060 ≤ position[i] < target1 ≤ speed[i] ≤ 106- Todas las posiciones son diferentes.
Ejemplos
- Entrada
- target = 20position = [14, 2, 8, 17, 0]speed = [3, 6, 4, 1, 2]
- Salida
- 2
- Explicación
- Por sí solos, los coches situados en las millas 17, 14, 8 y 2 necesitan 3, 2, 3 y 3 horas, así que el de la milla 14 alcanza al de la milla 17 y los otros dos los alcanzan en la milla 20. El coche situado en la milla 0 necesita 10 horas y llega solo.
- Entrada
- target = 9position = [0, 4, 7]speed = [1, 2, 3]
- Salida
- 3
- Explicación
- Los autos en las millas 7, 4 y 0 necesitan 2/3, 5/2 y 9 horas. Cada uno llegaría después del auto que tiene delante, así que nadie alcanza a nadie:
3flotas.
- Entrada
- target = 10position = [3]speed = [5]
- Salida
- 1
- Explicación
- Un coche en la carretera es una flota.
Para ir más allá
Las posiciones son enteros menores que target. ¿Puedes contar las flotas en tiempo O(n + target), sin una ordenación por comparación?
Pistas
Ábrelas de una en una. Cada una revela un poco más.
Los coches nunca pueden cambiar de orden. Para cada coche, calcula cuándo llegaría al destino si la carretera estuviera vacía. ¿Qué determina si alcanza alguna vez al coche que tiene delante?
Empieza por el coche más cercano al destino y avanza hacia atrás. Un coche se une a la flota de delante cuando llegaría como máximo al mismo tiempo que esa flota; de lo contrario, forma una nueva flota.
Ordena por posición, de mayor a menor, y mantén las flotas en una pila con la más reciente arriba. Compara los tiempos
d1/s1yd2/s2comod1 × s2frente ad2 × s1, usando enteros de 64 bits.
Solución
En un carril, los coches nunca cambian de orden, y lo que lo decide todo es cuándo llegaría cada coche por su cuenta: (target - position[i]) / speed[i]. Recorre los coches empezando por el más cercano al destino y avanzando hacia atrás. Un coche inicia una nueva flota solo cuando llegaría estrictamente más tarde que la flota que tiene delante.
Comprueba cada coche que tienes delante
Correcto, pero no termina con las pruebas más grandes
Intuición
Un automóvil lidera una flota exactamente cuando todos los automóviles que van delante de él llegarían estrictamente antes si fueran solos. Si algún automóvil que va delante no llegaría antes, tu automóvil lo alcanza a él o a su flota antes de llegar al destino. Si todos llegan antes, nada de lo que hay delante puede retrasarlo, porque una flota llega en el momento más tardío de llegada en solitario de sus automóviles. Cuenta los automóviles que lideran, comparando los tiempos exactamente mediante productos cruzados.
Cada automóvil recorre los n automóviles: 10^8 comprobaciones para n = 10^4.
Algoritmo
- Establece
fleets = 0. - Para cada coche
i, examina todos los cochesjconposition[j] > position[i]. - Si algún
jcumple(target - position[j]) × speed[i] ≥ (target - position[i]) × speed[j], el cocheies alcanzado: omítelo. - De lo contrario, el coche
ilidera una flota: suma 1 afleets. - Devuelve
fleets.
def carFleet(target, position, speed):
n = len(position)
fleets = 0
for i in range(n):
dist = target - position[i]
caught = False
for j in range(n):
# Car j is ahead and would not arrive before car i: car i catches it.
# (target - position[j]) / speed[j] >= dist / speed[i], without division.
if position[j] > position[i] and (target - position[j]) * speed[i] >= dist * speed[j]:
caught = True
break
if not caught:
fleets += 1
return fleetsOrdena por posición y apila las flotas
Intuición
Ordenados por posición, con el destino más cercano primero, los coches que van delante del actual son exactamente los que ya se han visto, los que ya están en flotas. Mantén las flotas en una pila, cada una almacenada como la distancia y la velocidad de su coche delantero, que determina el tiempo de llegada de la flota.
Solo importa la cima. Cada inserción llega estrictamente más tarde que la flota que tiene debajo, así que los tiempos aumentan de abajo hacia arriba, y llegar más tarde que la cima significa llegar más tarde que cualquier coche que va delante.
El Ejemplo 1, en orden, contiene los coches en 17, 14, 8, 2 y 0, con distancia sobre velocidad 3/1, 6/3, 12/4, 18/6, 20/2. Inserta (3, 1). El coche en 14 se une, ya que 6 × 1 > 3 × 3 es falso. El coche en 8 empata, 12 × 1 = 3 × 4, y se une, y lo mismo ocurre con el coche en 2. Para el coche en 0, 20 × 1 > 3 × 2: inserta.
Algoritmo
- Ordena los índices de los autos por posición, de mayor a menor.
- Empieza con una pila vacía de flotas.
- Para cada auto, calcula
dist = target - position[i]. - Si la pila está vacía o
dist × topSpeed > topDist × speed[i], inserta(dist, speed[i]); de lo contrario, el auto se une a la flota superior. - Devuelve el tamaño de la pila.
def carFleet(target, position, speed):
# Visit the cars from the one closest to the target backward.
order = sorted(range(len(position)), key=lambda i: position[i], reverse=True)
# One entry per fleet: (distance, speed) of the car at its front, which sets its arrival time.
stack = []
for i in order:
dist, spd = target - position[i], speed[i]
# dist / spd > top_dist / top_spd, compared without division:
# this car arrives after the fleet ahead, so it never catches it.
if not stack or dist * stack[-1][1] > stack[-1][0] * spd:
stack.append((dist, spd))
return len(stack)
Errores comunes y casos límite
- Contar un empate exacto como una flota nueva. Los coches en las millas 8 y 2 del ejemplo 1 llegan a la flota en la milla 20 y se unen a ella. Añade solo cuando el tiempo sea estrictamente posterior.
- Desbordamiento en el producto cruzado.
10^6 × 10^6 = 10^12no cabe en 32 bits: en Java, C, C++, C# y Rust, amplía a 64 bits antes de multiplicar; en R, usa números de punto flotante. - Ordenar en la dirección equivocada. Empezar por el coche más alejado del destino compara cada coche con los que tiene detrás, que nunca pueden bloquearlo.
- Ordenar solo
position. Ordena los índices o los pares (posición, velocidad) para que cada velocidad permanezca asociada a su coche.
Preguntas frecuentes3
¿Cuál es la complejidad temporal de Car Fleet?
Ordenar por posición toma O(n log n) y el recorrido con una pila toma O(n), así que el total es O(n log n) de tiempo y O(n) de memoria. Comprobar cada coche con respecto a cada coche que tiene delante toma O(n²).
¿Por qué Car Fleet usa una pila?
Al recorrer los coches desde el frente, cada coche nuevo solo tiene que compararse con la flota que tiene justo delante, la que se formó en último lugar. Una pila mantiene esa flota en la parte superior. Como solo se lee la parte superior, también bastan dos variables; además, la pila conserva las propias flotas.
¿Cómo comparas las horas de llegada sin usar números de punto flotante?
El tiempo de llegada es dist / speed. Como las velocidades son positivas, d1 / s1 > d2 / s2 se cumple exactamente cuando d1 × s2 > d2 × s1. Ambos lados son números enteros de hasta 10^12, así que calcúlalos con un tipo de 64 bits y la comparación será exacta, sin necesidad de tener en cuenta ningún redondeo.
Problemas similares
Problemas que usan las mismas ideas. Resolver dos o tres es lo que fija un patrón.
def carFleet(target, position, speed):
# Escribe el código aquíPrueba #1
Prueba #2
Prueba #3
Argumentos
target = 20 position = [14, 2, 8, 17, 0] speed = [3, 6, 4, 1, 2]
Salida Esperada
2