<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 Solution:
    def getCollisionTimes(self, cars: List[List[int]]) -> List[float]:
        # # different speeds, same directions
        # # one lane road

        # # cars[i] is [pos, speed]
        # #    pos_i < pos_j  for all i < j (sorted asc)
        
        # # cars are points: onliy when pos_i == pos_j do they collide
        
        # # when they collide, they form a new car with the slower of the two speeds

        # # so fast cars will collide with slow cars in front and effectively become a slow car

        # # return ans | ans[i] is the time at which car i collides with the next car
        # #                     or -1 if it doesn't collide at all

        # # usual trick to these is a combination of
        # #   > simplification: usually tracking cars explicitly is the hardest
        # #       > in this case fast cars are "absorbed" by slow cars so that helps
        # #       > and the position of the collided cars are just the position of the slowest car involved among all collisions
        # #         that's because the fast car no longer exists, its hypothetical farther position isn't relevant
        # #   > correct direction: solving left-to-right or right-to-left

        # # edge case:
        # #    really fast, very slow, slowest
        # # x       0          100        110
        # # v      101           1         1.1
        # #
        # #   reallyFast hits verySlow at t=1, position 101
        # #   verySlow hits slowest at t=100
        
        # # have to resolve collisions left to right because really fast will hit very slow before very slow hits slowest
        # # but it's also possible that very slow hits slowest first as well

        # # so we must be very clever here
        # # but also we can use the simplifications above to help us

        # # when's the next collision time? look at pairs of cars and calculate the collision time
        # # put them in a heap (?)
        # # while there are collision times on the heap:
        # #    pop the time and the indices involved
        # #    out[lowerIndex] = collisionTime
        # #    and now the prior uncollided car before lowerIndex needs to know about this collision
        # #    and we need to know in O(1) because there are 1e5 cars to handle

        # # another insight: contiguous regions of cars will collide in a big pileup

        # # after drawing out a few examples:
        # #    remember that we collide with a car and take the slower, farther car as a result
        
        # # so the collision time for i, i+1 does NOT depend on earlier cars j < i
        # #     either those cars are slower and the collision time doesn't matter
        # #     or those cars are faster, and collided with earlier cars or this car

        # #### hard problem to get right, need lots of insights. bad interview question

        # # let's do the UF one

        # # union by rank: let UF do it's thing in finding roots
        # # a group of cars is [lo, hi] index range where they've all collided with with the hi car
        # # we can track roots to hopefully keep things simple
        # # if two roots collide, then we have
        # #           r1,x1,v1       r2,x2,v2     r3,x3,v3       r4,x4,v4
        # # suppose 2 and 3 collide next
        # #
        # #   then we have
        # #       > mark 2 (specifically the hi car of 2) as having collided with three at the collision time
        # #       > 3-4 collision time does NOT change
        # #       > 1-2 collision no longer exists, because 2 doesn't exist - it was replaced with 3
        # #          > so we need to push the updated (lower?) collision time of 1-3
        # #          > AND we need to make sure we don't process the original 1-2 collision because that's not valid any more
        # #  So before marking collision times, we can check if the pushed collision time is still correct.

        # N = len(cars)
        # parent = [-1]*N
        # # index arrays only valid for roots
        # hiIdx = list(range(N)) # the slow car each cluster has merged into, also always the max index in the range
        # loIdx = list(range(N)) # earliest car that has merged into this cluster

        # def find(u: int) -> int:
        #     if parent[u] < 0: return u
        #     parent[u] = find(parent[u])
        #     return parent[u]

        # def union(u: int, v: int) -> None:
        #     ru = find(u)
        #     rv = find(v)
        #     if ru == rv: return

        #     if parent[rv] < parent[ru]:
        #         ru, rv = rv, ru

        #     hiIdx[ru] = max(hiIdx[ru], hiIdx[rv])
        #     loIdx[ru] = min(loIdx[ru], loIdx[rv])
        #     parent[ru] += parent[rv]
        #     parent[rv] = ru

        # collisions = [] # (time, earlierCar, laterCar)
        # for i in range(N-1):
        #     x1, v1 = cars[i]
        #     x2, v2 = cars[i+1]
        #     if v1 > v2:
        #         t = (x2-x1)/(v1-v2)
        #         collisions.append((t, i, i+1))

        # heapify(collisions)
        # ans = [-1]*N

        # while collisions:
        #     t, u, v = heappop(collisions)

        #     # when we collide, the two cars are replaced with just the slow car in front
        #     # therefore if u or v aren't the front car any more then this is a stale entry
        #     if u != hiIdx[find(u)]: continue
        #     if v != hiIdx[find(v)]: continue

        #     union(u, v) # collide
        #     ans[u] = t

        #     # now that u and v have collided, the effective car behind u has a new collision time
        #     p = loIdx[find(u)]-1
        #     if p < 0: continue # no prior effective car
        #     # otherwise p is the highest possible index of that prior group: it's the slow car for sure
        #     px, pv = cars[p]
        #     u = hiIdx[find(u)] # replace u with the effective car of this collision: the highest index
        #     ux, uv = cars[u]
        #     if pv > uv:
        #         # new/updated collision time
        #         t = (ux-px) / (pv - uv)
        #         heappush(collisions, (t, p, u))

        # return ans

        #### cheated and peeked at the fastest solution. it's a stack, process right to left as I started with

        # if last car is fast, it never collides. skip
        # if last car is slow, push to stack?
        
        # later cars:
        #       if car will collide with the next car, we know it will collide with something later
        #       but we don't yet know when it will collide (?) because it depends on the times of the later collisions and the resulting speed
        

        # fast verySlow slowest example: we can have fast-verySlow first, or verySlow-slowest first

        # why not collide verySlow-slowest immediately?
        #      because we only "merge" verySlow into slowest at t23
        #      if t12 for fast-verySlow is <= t23: fast collides with verySlow first
        #      if t12 for fast-verySlow is >  t23: fast collides with slowest
        #     so we know the order is verySlow-slowest collision happens first -> we can go ahead and process that result

        # so the idea is we have a stack of pending collisions, by time decreasing
        #  if i collides with next car (top of stack) at t < stack[-1] then we have a new earliest time and higher velocity
        #     so we need to push this in case a later car needs it
        #  else we know that collision will happen first, then we repeat. Eventually the present car will either lead a new peloton
        #     or collide with the next and we'll push it

        # maybe an easier way: cars collide in contiguous groups; the lead car is the ultimate result of the collision
        
        # suppose we have effective cars a, b, c   that will collide
        #         <-------------|--------------|--------------
        #                     t_ab            t_bc
        #                va          vb              vc
        #
        #
        # now look at a prior car that will collide with a at t
        #    if t >= t_ab: t collides with result of ab. handle ab collision and repeat
        #    if t < t_ab

        #### UGHHHHHH

        # effective velocity of car in front declines over time
        # current car needs to know its collision time, which depends on the effective x and v of the car in front when that happens
        
        # okay I think it's easier than I thought:
        #   > collisions result in an "effective car" with (x, v) equal to the slower of the two
        #   > this means many collisions result in a single (x, v) of the slowest car
        #   > as collisions happen the speed of the lead car declines
        #   > so suppose we have cars b, c
        #   > and we look at a: a collides with b if b-c happens after a-b
        #                       a collides with c if b-c happens before a-b
        # > CARS ONLY COLLIDE WITH THE EFFECTIVE CAR AHEAD
        # so we know the collision time for i immediately upon processing i
        # it's for the sake of earlier cars j < i that we have the velocity profile

        N = len(cars)
        out = [-1]*N
        ahead = [] # (t, x, v) effective positions and times of cars ahead
        for i in range(N-1, -1, -1):
            x, v = cars[i]

            # the idea is that the result of later cars colliding might be
            #    > a fast effective car until t[-1]
            #    > then a slower effective car until t[-2]
            #    > even slower effective car until t[-3]
            #    > etc.
            # we collide with the fast car if our collision with it would occur at t <= t[-1]. Otherwise that faster
            # car collides with a later one, and we see if we collide with the next one

            while ahead:
                tf, xf, vf = ahead[-1] # effective vel and posn of next car, valid for t < tf
                if v <= vf: ahead.pop() # we'll never collide with that next car
                elif (xf-x)/(v-vf) >= tf: ahead.pop() # next car won't exist by the time we collide with it
                else: break

            if ahead:
                _, xf, vf = ahead[-1]
                t = (xf-x)/(v-vf)
                out[i] = t
                ahead.append((t, x, v))
            else:
                ahead.append((math.inf, x, v))

        return out
1109