<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>

r'''
# Requirements

n = len(cars)
1 <= n <= ?
len(cars[i]) == 2
1 <= position, speed <= 1,000,000
cars[i][0] < cars[i + 1][0]

# Edge cases

1. A faster car joins a slower car, and caught up by a slower car

2. The car never catch up any cars
    - Put -1

# Solutions

1. Brute force, simulation
    - O(nk) time, O(n) auxiliary space, where k = max distance between two cars
2. Better brute force
    - O(n^2) time, O(1) auxiliary space
2. Monotonic stack
    - O(n) time, O(n) auxiliary space

(3,4),(5,4),(6,3),(9,1)

(4,5),(5,5),(6,9),(7,5),(8,4),(9,1)
 1.25   1    0.25  0.5   0.33  -1
              ^
stack=(9,1),(8,4)
'''
class Solution:
    def getCollisionTimes(self, cars: list[list[int]]) -> list[float]:
        n = len(cars)
        stack, collisions = [], [-1] * n

        def collide_at(a: list[int], b: list[int]) -> float:
            return (b[0] - a[0]) / (a[1] - b[1])

        for i in range(n - 1, -1, -1):
            while stack and cars[i][1] <= cars[stack[-1]][1]:
                stack.pop()
            while stack and collide_at(cars[i], cars[stack[-1]]) > collisions[stack[-1]] > 0:
                stack.pop()

            if stack:
                collisions[i] = collide_at(cars[i], cars[stack[-1]])
            stack.append(i)

        return collisions
1340