Planteamiento y contexto
Este es un problema voraz con restricciones de recursos. El combustible solo se puede tomar de estaciones por las que ya se ha pasado, y el objetivo es el número de paradas en lugar del combustible total. Una respuesta sólida en la entrevista conecta la alcanzabilidad, las decisiones perezosas (lazy), el invariante del max-heap y el tramo final desde la última estación hasta el destino.
Qué evalúa el entrevistador
- Si conviertes "reabastecer solo cuando sea necesario" en una estrategia voraz perezosa.
- Si demuestras que tomar la mayor cantidad de combustible pasado no puede incrementar el conteo óptimo de paradas.
- Si manejas el inicio, el destino, las posiciones duplicadas y los casos inalcanzables.
- Si proporcionas una implementación con tiempo O(n log n) y espacio O(n).
Preguntas para clarificar
Confirma que las estaciones estén ordenadas por posición, si se permiten posiciones duplicadas, que el combustible sea no negativo y si el destino en sí es una estación. Pregunta sobre el tamaño de la entrada y el rango de enteros. El modelo por defecto comienza en la posición 0 y permite tomar combustible de una estación solo después de haber llegado a ella.
Esquema de respuesta en 30 segundos
Recorre las estaciones por posición e inserta cada cantidad de combustible visitada en un max heap. Antes de llegar a cada siguiente estación o al destino, resta la distancia. Si el combustible se vuelve negativo, se fuerza una parada, por lo que se extrae repetidamente el combustible más grande pasado y se incrementa el conteo de paradas. Si el heap está vacío, devuelve -1. Elegir el combustible más grande disponible en cada parada forzada maximiza la distancia alcanzable sin aumentar el número de paradas.
Solución paso a paso
1. Establecer el invariante de alcanzabilidad
En la posición p, el heap contiene el combustible de cada estación en o antes de p, mientras que fuel es la cantidad no utilizada. Si la cantidad de combustible es negativa, avanzar es imposible sin usar una de esas estaciones. Cada extracción amplía el rango alcanzable hasta que la cantidad de combustible vuelve a ser no negativa.
2. Demostrar la elección voraz perezosa
Supongamos que un plan óptimo elige una cantidad pasada menor a cuando debe reabastecer, mientras que una cantidad mayor b está disponible. Reemplaza a con b: el conteo de paradas no cambia y el combustible restante después de este punto no disminuye, por lo que cada tramo posterior sigue siendo factible. Repetir este intercambio produce un plan igualmente óptimo que siempre elige el máximo.
3. Tratar el destino como un límite
Agrega una estación virtual (target, 0) y procésala exactamente como cualquier otra posición. Comienza desde la posición 0, resta cada distancia y solo entonces agrega el combustible de la estación. Si el destino aún requiere una extracción, esas paradas cuentan; un heap vacío mientras el combustible es negativo significa que el destino es inalcanzable.
4. Implementar el heap
heapq de Python es un min heap, por lo que los valores de combustible negativos simulan un max heap. Cada estación se inserta una vez y solo se extrae cuando se requiere una parada:
import heapq
def min_refuel_stops(target, start_fuel, stations):
fuel = start_fuel
previous = 0
max_heap = []
stops = 0
for position, station_fuel in [*stations, (target, 0)]:
fuel -= position - previous
while fuel < 0 and max_heap:
fuel += -heapq.heappop(max_heap)
stops += 1
if fuel < 0:
return -1
heapq.heappush(max_heap, -station_fuel)
previous = position
return stops5. Analizar complejidad y límites
Con n estaciones, cada valor de combustible entra y sale del heap a lo sumo una vez, lo que da un tiempo O(n log n) y un espacio de heap O(n). Prueba con combustible inicial suficiente, una primera estación inalcanzable, una parada requerida después de la última estación, combustible cero, posiciones duplicadas, una llegada exacta al destino y un destino inalcanzable.
Respuesta modelo de alta calidad
Agregarúa el destino como una estación virtual con combustible cero. Durante el recorrido, restaría la distancia de viaje e insertaría el combustible de las estaciones ya alcanzadas. Siempre que el combustible restante sea negativo, se fuerza una parada; se toma repetidamente el combustible histórico más grande hasta que la posición actual sea alcanzable. Un heap vacío significa -1. La prueba de intercambio reemplaza cualquier combustible pasado menor elegido por uno disponible más grande sin aumentar las paradas ni reducir la alcanzabilidad futura. Cada estación se inserta y extrae a lo sumo una vez, por lo que la complejidad es de tiempo O(n log n) y espacio O(n).
Errores comunes
- Reabastecer inmediatamente en cada estación en lugar de retrasar la decisión.
- Comprobar solo los espacios entre estaciones y olvidar el tramo final hacia el destino.
- Mezclar el combustible actual no utilizado con el combustible disponible en el heap.
- Usar un min heap y tomar la cantidad más pequeña.
- Agregar una estación antes de alcanzarla y usar combustible futuro antes de tiempo.
- Probar solo ejemplos alcanzables y omitir los límites de heap vacío o numéricos.
Preguntas de seguimiento
¿Por qué no tomar el máximo en cada estación?
El objetivo es el conteo de paradas. Reabastecer temprano puede agregar paradas sin mejorar la alcanzabilidad. Retrasar hasta que el combustible sea insuficiente asegura que cada parada responda a una restricción real.
¿Qué cambia si se permite el reabastecimiento parcial?
El estado y la función de costo cambian. Los precios o la capacidad del tanque pueden importar, por lo que la demostración para tomar todo el combustible de una estación ya no se aplica directamente.
¿Por qué funcionan las posiciones duplicadas?
Su distancia es cero, por lo que se pueden insertar en cualquier orden. El heap aún expone la mayor cantidad disponible cuando un tramo posterior realmente requiere combustible.
¿Cómo devolverías las paradas reales?
Almacena el índice de la estación con cada valor del heap y registra el índice cada vez que se extraiga. Ordena los índices registrados por posición o por orden de selección para reconstruir la ruta.