<p>There are <code>n</code> cars traveling at different speeds in the same direction along a one-lane road. You are given an array <code>cars</code> of length <code>n</code>, where <code>cars[i] = [position<sub>i</sub>, speed<sub>i</sub>]</code> represents:</p>

<ul>
	<li><code>position<sub>i</sub></code> is the distance between the <code>i<sup>th</sup></code> car and the beginning of the road in meters. It is guaranteed that <code>position<sub>i</sub> &lt; position<sub>i+1</sub></code>.</li>
	<li><code>speed<sub>i</sub></code> is the initial speed of the <code>i<sup>th</sup></code> car in meters per second.</li>
</ul>

<p>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 <strong>slowest</strong> car in the fleet.</p>

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

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> cars = [[1,2],[2,1],[4,3],[7,2]]
<strong>Output:</strong> [1.00000,-1.00000,3.00000,-1.00000]
<strong>Explanation:</strong> 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.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> cars = [[3,4],[5,4],[6,3],[9,1]]
<strong>Output:</strong> [2.00000,1.00000,1.50000,-1.00000]
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= cars.length &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= position<sub>i</sub>, speed<sub>i</sub> &lt;= 10<sup>6</sup></code></li>
	<li><code>position<sub>i</sub> &lt; position<sub>i+1</sub></code></li>
</ul>

from typing import List


class Solution:
    def getCollisionTimes(self, cars: List[List[int]]) -> List[float]:
        n = len(cars)
        result = [-1.0] * n
        stack = []  # Stack to store indices of cars

        for i in range(n - 1, -1, -1):
            # Calculate collision time with cars on top of the stack
            while stack:
                top = stack[-1]
                # If the current car is slower than the top car on the stack
                if cars[i][1] <= cars[top][1]:
                    stack.pop()
                else:
                    # Calculate the time for the current car to catch up with the top car
                    time_to_collision = (cars[top][0] - cars[i][0]) / (cars[i][1] - cars[top][1])
                    # Check if the top car will reach the end before or at the same time as the current car
                    if result[top] == -1 or time_to_collision <= result[top]:
                        result[i] = time_to_collision
                        break
                    stack.pop()

            # Push current car to the stack
            stack.append(i)

        return result


# Driver code for testing
def test_solution():
    sol = Solution()

    # Test case 1
    cars1 = [[1, 2], [2, 1], [4, 3], [7, 2]]
    print(f"Input: {cars1}")
    print(f"Output: {sol.getCollisionTimes(cars1)}")
    # Expected: [1.00000, -1.00000, 3.00000, -1.00000]

    # Test case 2
    cars2 = [[3, 4], [5, 4], [6, 3], [9, 1]]
    print(f"Input: {cars2}")
    print(f"Output: {sol.getCollisionTimes(cars2)}")
    # Expected: [2.00000, 1.00000, 1.50000, -1.00000]

    # Test case 3
    cars3 = [[1, 2], [2, 1], [4, 3]]
    print(f"Input: {cars3}")
    print(f"Output: {sol.getCollisionTimes(cars3)}")
    # Expected: [1.00000, -1.00000, -1.00000]

    # Test case 4
    cars4 = [[10, 5], [20, 5], [30, 5]]
    print(f"Input: {cars4}")
    print(f"Output: {sol.getCollisionTimes(cars4)}")
    # Expected: [-1.00000, -1.00000, -1.00000]

    # Test case 5
    cars5 = [[1, 3], [5, 2], [10, 1]]
    print(f"Input: {cars5}")
    print(f"Output: [2.00000, 5.00000, -1.00000]")


# Run the driver code
test_solution()


669