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

class Car:
    def __init__(self, pos, speed, idx, prev=None, next=None):
        self.pos = pos
        self.speed = speed
        self.idx = idx
        self.prev = prev
        self.next = next

class Solution:
    def getCollisionTimes(self, cars: List[List[int]]) -> List[float]:
        colis_times = [-1] * len(cars)
        cars = [Car(pos, sp, i) for i, (pos, sp) in enumerate(cars)]
        for i in range(len(cars)-1): cars[i].next = cars[i+1]
        for i in range(1, len(cars)): cars[i].prev = cars[i-1]
        
        catchup_order = [((b.pos-a.pos)/(a.speed-b.speed), a.idx, a)
                        for i, (a, b) 
                        in enumerate(zip(cars, cars[1:])) if a.speed > b.speed]
        heapify(catchup_order)
        
        while catchup_order:
            catchup_time, idx, car = heappop(catchup_order)
            if colis_times[idx] > -1: continue # ith car has already caught up
            colis_times[idx] = catchup_time
            if not car.prev: continue # no car is following us
            car.prev.next, car.next.prev = car.next, car.prev
            if car.next.speed >= car.prev.speed: continue # the follower is too slow to catch up
            new_catchup_time = (car.next.pos-car.prev.pos)/(car.prev.speed-car.next.speed)
            heappush(catchup_order, (new_catchup_time, car.prev.idx, car.prev))
        
        return colis_times
1687