1776. Car Fleet II

There are n cars traveling at different speeds in the same direction along a one-lane road. You are given an array cars of length n, where cars[i] = [positioni, speedi] represents:

• positioni is the distance between the ith car and the beginning of the road in meters. It is guaranteed that positioni < positioni+1.

• speedi is the initial speed of the ith car in meters per second.

For simplicity, cars can be considered as points moving along the number line. Two cars collide when they occupy the same position. Once a car collides with another car, they unite and form a single car fleet. The cars in the formed fleet will have the same position and the same speed, which is the initial speed of the slowest car in the fleet.

Return an array answer, where answer[i] is the time, in seconds, at which the ith car collides with the next car, or -1 if the car does not collide with the next car. Answers within 10-5 of the actual answers are accepted.

Example 1:

Input: cars = [[1,2],[2,1],[4,3],[7,2]]
Output: [1.00000,-1.00000,3.00000,-1.00000]
Explanation: After exactly one second, the first car will collide with the second car, and form a car fleet with speed 1 m/s. After exactly 3 seconds, the third car will collide with the fourth car, and form a car fleet with speed 2 m/s.

Example 2:

Input: cars = [[3,4],[5,4],[6,3],[9,1]]
Output: [2.00000,1.00000,1.50000,-1.00000]

Constraints:

• 1 <= cars.length <= 105

• 1 <= positioni, speedi <= 106

• positioni < positioni+1

Solution

The list is already sorted by position.

We need to check each ahead car to know if a collision happens.

If a collision happens, the time spent should be calculated by the car fleet head and the current car.

A collision with aheadCar happened if they satisfy the below criteria

1. Ahead Car is slower than the current Car

2. Ahead Car's collision with its previous car (if any) happens after the collision with current Car

If they are statisfied, it would be the car fleet head.

We keep tracking the ahead cars to find a suitable collision measure point (which is the head of the ahead car fleet). One thing to note is that if the aHead car can't be the car fleet head of my current car, it is impossible to be the car fleet head for the remained cars. -> We can use Stack to track the car fleet head.

    public double[] getCollisionTimes(int[][] cars) {
        int n = cars.length;
        double[] ret = new double[n];
        Stack<Integer> aHeadCars = new Stack<>();
        
        for(int i = n-1; i >= 0; i--) {
            int position = cars[i][0];
            int speed = cars[i][1];
            double timeSpend = -1;
            while(!aHeadCars.isEmpty()){
                int index = aHeadCars.peek();
                int aHeadPosition = cars[index][0];
                int aHeadSpeed = cars[index][1];
                if(aHeadSpeed >= speed) {
                    aHeadCars.pop();
                    continue;
                }
                timeSpend = (double)( aHeadPosition - position ) / (speed - aHeadSpeed); ;                

                if(ret[index] != -1 && timeSpend >= ret[index]){
                    aHeadCars.pop();
                    continue;
                } else{
                    break;
                }
            }
            
            if(aHeadCars.isEmpty()){
                ret[i] = -1;
            }else{
                ret[i] = timeSpend;
            }
            aHeadCars.push(i);
        }
        return ret;
    }