Car Fleet

Last updated Jun 15, 2023 Edit Source

• Interviewprep

Car Fleet es un problema de Leetcode marcado en la categoria “Medium”. El problema dicta lo siguiente:

Se tienen un grupo de coches, representados por un array llamado position, un ejemplo de valores seria [10, 8, 0, 5, 3]. A su vez, existe un array llamado speed, un ejemplo de sus valores serian [2, 4, 1, 1, 3]. Un carro se ve representado por dos cosas su posicion y su velocidad, los indices son equivalentes entre arrays, es decir que el carro 0 tiene una posicion 10 con velocidad 2. La meta esque estos coches lleguen a un punto, llamado target. El problema aqui esque se busca determinar la cantidad de car fleets que existirian a dicho punto target. Un car fleet es basicamente lo que ocurre debido a que unos coches van mas rapido que otros y por tanto estos deberian de ser capaces de poder alcanzar a los que se encuentran delante de ellos, la cosa esque el camino es de 1 solo carril, por tanto, los que van mas rapido deben disminuir su velocidad para ir al paso del que va enfrente de ellos. A dos coches que van en la “misma posicion” con la “misma velocidad” (debido a que esta necesita disminuir cuando van juntos) se le llama car fleet.

Para entender esta solucion hay cosas que hay que tener en cuenta:

1. ¿Cuál es la UNICA forma de que se forme un Car Fleet?. Solo ocurre si un coche que VA RAPIDO alcanza a un coche que VA MAS LENTO Y QUE SE ENCUENTRA DELANTE DE EL. Gracias a esto, podemos saber que lo mas efectivo seria ordenar la lista e iterar sobre ella en orden descendiente, debido a que estamos interesados en los car fleets y estos solo se forman del coche de adelante hacia los coches de atras, en caso de que un coche de adelante sea adelantado significa que este es mas lento que su anterior y por tanto bajarian su velocidad SIEMPRE a la suya.
2. ¿Cómo podemos determinar si un coche que esta detras de otro es mas rapido que este?. Lo poco practico seria iterar y realizar los saltos para saber quien llegar primero, esto es demasiado complicado. La forma sencilla es determinar la cantidad de “saltos” restantes que un coche tiene que dar para llegar a la meta. La forma de calcular esto es hacer: (posicion_destino - coche_posicion_actual) / coche_velocidad. De esta forma determinamos cuantas veces se tiene que desplazar el coche para llegar a la meta, los coches rapidos les tomara menos y a los coches lentos les tomara mas.

Conociendo lo anterior, podemos determinar tambien que una Stack seria lo mas adecuado para resolver este problema. Esto es debido a que podemos agregar la cantidad de saltos restantes del coche actual (Recordemos que iteraremos de mayor a menor) y despues podemos consultar ese “top” de la stack en iteraciones posteriores. En caso de que en un futuro los saltos restantes de un coche sean menores que el “top” de la stack significa que nuestro nuevo coche disminuira su velocidad y formara un car fleet con el, por tanto, es irrelevante colocarlo en el stack.

Aplicando lo anterior, podemos la solucion ahora solo mirando a la longitud que tiene la stack, debido a que en ella ya se encuentran los car fleets y las velocidades a las que llegaron.

Finalmente, con estos datos, podemos elaborar una solucion:

1. Ordenar la lista por los valores de position de forma descendente.
2. Iteras sobre ella de mayor a menor.
3. Calcular a cantidad de saltos restantes del coche actual
4. En caso de encontrarte con una stack vacia, simplemente agregar la cantidad de saltos restantes
5. En caso de que no, compararse con el tope de la stack.
6. Si es mayor que el tope de la stack (Le tomara mayor cantidad de saltos llegar al target) simplemente agregar la cantidad de saltos.
7. Si es menor o igual que el tope de la stack (Será mas rapido que el tope de la stack) no te agregues y sigue iterando
8. Finalmente, al finalizar la iteracion se retorna la longitud de dicha stack y se obtiene el resultado

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

// target: 12
// position: [10, 8, 0, 5, 3]
// speed: [2, 4, 1, 1, 3]
function carFleet(target: number, position: number[], speed: number[]): number {
    const tempCars = [];
    for (let i = 0; i < position.length; i++) {
        tempCars.push({
            position: position[i],
            speed: speed[i],
        });
    }

    const cars = tempCars.sort((a, b) => b.position - a.position) // 1. [{10, 2}, {8, 4}, {5, 1}, {3, 3}, {0, 1}]
    const stack = [];

    for (const car of cars) { // 2. Se itera de mayor a menor (Izquierda a derecha del comentario anterior)
        const jumpsLeft = (target - car.position) / car.speed; // 3. Cantidad de Saltos Restantes

        if (!stack.length) {
            stack.push(jumpsLeft); // 4. Agregar si se encuentra vacia el stack
        }

        const topJumpsLeft = stack[stack.length-1]; // 5. Tope del Stack
        
        if (jumpsLeft > topJumpsLeft) { // 5. Comparacion
            stack.push(jumpsLeft) // 6. Si te toma mas saltos llegar agregate
        } else {
            continue // 7. Si no no te agregues y continua
        }
    }
    return stack.length; // 8. Retorna el tope

}