<p>There are <code>n</code> <strong>1-indexed</strong> robots, each having a position on a line, health, and movement direction.</p>

<p>You are given <strong>0-indexed</strong> integer arrays <code>positions</code>, <code>healths</code>, and a string <code>directions</code> (<code>directions[i]</code> is either <strong>&#39;L&#39;</strong> for <strong>left</strong> or <strong>&#39;R&#39;</strong> for <strong>right</strong>). All integers in <code>positions</code> are <strong>unique</strong>.</p>

<p>All robots start moving on the line<strong> simultaneously</strong> at the <strong>same speed </strong>in their given directions. If two robots ever share the same position while moving, they will <strong>collide</strong>.</p>

<p>If two robots collide, the robot with <strong>lower health</strong> is <strong>removed</strong> from the line, and the health of the other robot <strong>decreases</strong> <strong>by one</strong>. The surviving robot continues in the <strong>same</strong> direction it was going. If both robots have the <strong>same</strong> health, they are both<strong> </strong>removed from the line.</p>

<p>Your task is to determine the <strong>health</strong> of the robots that survive the collisions, in the same <strong>order </strong>that the robots were given,<strong> </strong>i.e. final health of robot 1 (if survived), final health of robot 2 (if survived), and so on. If there are no survivors, return an empty array.</p>

<p>Return <em>an array containing the health of the remaining robots (in the order they were given in the input), after no further collisions can occur.</em></p>

<p><strong>Note:</strong> The positions may be unsorted.</p>

<div class="notranslate" style="all: initial;">&nbsp;</div>

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

<p><img height="169" src="https://assets.leetcode.com/uploads/2023/05/15/image-20230516011718-12.png" width="808" /></p>

<pre>
<strong>Input:</strong> positions = [5,4,3,2,1], healths = [2,17,9,15,10], directions = &quot;RRRRR&quot;
<strong>Output:</strong> [2,17,9,15,10]
<strong>Explanation:</strong> No collision occurs in this example, since all robots are moving in the same direction. So, the health of the robots in order from the first robot is returned, [2, 17, 9, 15, 10].
</pre>

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

<p><img height="176" src="https://assets.leetcode.com/uploads/2023/05/15/image-20230516004433-7.png" width="717" /></p>

<pre>
<strong>Input:</strong> positions = [3,5,2,6], healths = [10,10,15,12], directions = &quot;RLRL&quot;
<strong>Output:</strong> [14]
<strong>Explanation:</strong> There are 2 collisions in this example. Firstly, robot 1 and robot 2 will collide, and since both have the same health, they will be removed from the line. Next, robot 3 and robot 4 will collide and since robot 4&#39;s health is smaller, it gets removed, and robot 3&#39;s health becomes 15 - 1 = 14. Only robot 3 remains, so we return [14].
</pre>

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

<p><img height="172" src="https://assets.leetcode.com/uploads/2023/05/15/image-20230516005114-9.png" width="732" /></p>

<pre>
<strong>Input:</strong> positions = [1,2,5,6], healths = [10,10,11,11], directions = &quot;RLRL&quot;
<strong>Output:</strong> []
<strong>Explanation:</strong> Robot 1 and robot 2 will collide and since both have the same health, they are both removed. Robot 3 and 4 will collide and since both have the same health, they are both removed. So, we return an empty array, [].</pre>

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

<ul>
	<li><code>1 &lt;= positions.length == healths.length == directions.length == n &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= positions[i], healths[i] &lt;= 10<sup>9</sup></code></li>
	<li><code>directions[i] == &#39;L&#39;</code> or <code>directions[i] == &#39;R&#39;</code></li>
	<li>All values in <code>positions</code> are distinct</li>
</ul>

from queue import PriorityQueue
from queue import deque

class Solution:
    def survivedRobotsHealths(self, positions: List[int], healths: List[int], directions: str) -> List[int]:
        stack = []
        for i in sorted(range(len(positions)), key = lambda i: positions[i]):
            if directions[i] == 'R':
                stack.append(i)
            else:
                while stack and healths[stack[-1]] < healths[i]:
                    healths[i] -= 1
                    healths[stack.pop()] = 0
                if stack:
                    if healths[stack[-1]] == healths[i]:
                        healths[stack.pop()] = 0
                    else:
                        healths[stack[-1]] -= 1
                    healths[i] = 0
        return [h for h in healths if h] 

        class Robot:
            def __init__(self, name, position, health, direction):
                self.name = name
                self.position = position
                self.health = health
                self.direction = 1 if direction == 'R' else -1
            

            def __repr__(self):
                return f"Robot {self.name}: ({self.position}, {self.health}, {self.direction})"
            

        robots = [Robot(i, p, h, d) for i, (p, h, d) in enumerate(zip(positions, healths, directions))]

        robots.sort(key=lambda r: r.position)
        robots = deque(robots)
        #print([r for r in robots])
        moves_to_collide = max(positions) - min(positions)
        no_collisions = 0
        width = max(r.position for r in robots) - min(r.position for r in robots)
        last_width = width + 1
        #while no_collisions < moves_to_collide:
        while any(r.direction == 1 for r in robots) and any(r.direction == -1 for r in robots):
        #while True:
            for r in robots:
                r.position += r.direction
            survivors = deque()
            for r in robots:
                if not survivors:
                    survivors.append(r)
                    continue
                if r.position > survivors[-1].position:
                    survivors.append(r)
                    continue
                if r.health == survivors[-1].health:
                    r.health = 0
                    survivors[-1].health = 0
                    survivors.pop()
                    continue
                if r.health > survivors[-1].health:
                    survivors[-1].health = 0
                    r.health += -1
                    survivors.pop()
                    survivors.append(r)
                    continue
                survivors[-1].health += -1
                r.health = 0
            if len(robots) == len(survivors):
                no_collisions += 1
            else:
                no_collisions = 0
            robots = survivors

            last_width = width
            if len(robots) < 1:
                break
            width = max(r.position for r in robots) - min(r.position for r in robots)
            if width > last_width:
                break

        return [r.health for r in sorted(robots, key=lambda r: r.name) if r.health > 0]


        if len(positions) <= 1:
            return healths
        robots = [(i, p, h, (1 if d == 'R' else -1)) for i, (p, h, d) in enumerate(zip(positions, healths, directions))]

        q = PriorityQueue()
        for r1, r2 in combinations(robots, 2):
            i1, p1, h1, d1 = r1
            i2, p2, h2, d2 = r2
            if d1 == d2:
                continue
            t = (p2 - p1) / (d1 - d2)
            if t < 0:
                continue
            q.put((t, i1, i2))
        
        while not q.empty():
            t, i1, i2 = q.get()
            #print(t, i1, i2)
            i1, p1, h1, d1 = robots[i1]
            i2, p2, h2, d2 = robots[i2]
            if h1 == 0 or h2 == 0:
                continue
            if h1 == h2:
                robots[i1] = (i1, p1, 0, d1)
                robots[i2] = (i2, p2, 0, d2)
                continue
            if h1 > h2:
                robots[i1] = (i1, p1, h1 - 1 if h1 > 0 else 0, d1)
                robots[i2] = (i2, p2, 0, d2)
                continue
            robots[i2] = (i2, p2, h2 - 1 if h2 > 0 else 0, d2)
            robots[i1] = (i1, p1, 0, d1)

        survivors = [(r[0], r[2]) for r in robots if r[2] > 0]
        return [h for (i, h) in survivors]
        


        robots.sort()
        robots_last = robots.copy()

        moves_to_collide = max(positions) - min(positions)
        moves_to_collide *= 2
        #print(moves_to_collide)
        no_collision_count = 0
        while no_collision_count < moves_to_collide:
            #print(robots)
            robots = [(p + d, i, h, d) for p, i, h, d in robots]
            for i, (r1, r2) in enumerate(zip(robots, robots[1:])):
                if r1[0] < r2[0]:
                    continue
                if r1[2] == r2[2]:
                    robots[i] = (0, 0, 0, 0)
                    robots[i + 1] = (0, 0, 0, 0)
                    continue
                if r1[2] > r2[2]:
                    robots[i] = (r1[0], r1[1], r1[2] - 1 if r1[2] > 0 else 0, r1[3])
                    robots[i + 1] = (0, 0, 0, 0)
                    continue
                robots[i + 1] = (r2[0], r2[1], r2[2] - 1 if r2[2] > 0 else 0, r2[3])
                robots[i] = (0, 0, 0, 0)
            robots = [r for r in robots if r[2] > 0]
            robots.sort()
            no_collision_count = (no_collision_count + 1) if len(robots) == len(robots_last) else 0
            robots_last = robots.copy()
        survivors = [(r[1], r[2]) for r in robots]
        survivors.sort()
        return [h for (i, h) in survivors]
893