Last Time an Object Leaves a Table When Colliding Objects Swap Velocities

A table is the segment from position 0 (its left edge) to position `table_length` (its right edge). Object `i` starts at `position[i]` and moves at the constant velocity `velocity[i]`; a positive velocity moves it to the right and a negative velocity moves it to the left. All objects start moving at time 0. When two objects meet they collide and exchange velocities, and an object is removed from the table as soon as it reaches either edge. Return the time at which the last object leaves the table, rounded up to an integer. The report states the collision and removal rules and the rounding, but not whether starting positions can repeat or what happens when three or more objects meet at once; this version makes the positions distinct and fixes the multi-object case in Rules below. ### Function Signature ```python def last_exit_time(position: list[int], velocity: list[int], table_length: int) -> int: ``` ### Rules - Objects are points. Between collisions, an object at position `p` with velocity `v` is at `p + v * t` after `t` more time units. - Two objects collide whenever they are at the same point at the same moment, whether they are moving toward each other or one is catching up with another moving in the same direction. Each continues from that point with the other's velocity. - If three or more objects are at the same point at the same moment, they leave it with the velocities they arrived with, redistributed so that their left-to-right order does not change: list the objects from left to right as they were just before the meeting, and the `k`-th object in that list leaves with the `k`-th smallest of those velocities. For two objects this is the same as exchanging velocities. - An object is removed at the exact moment it reaches position 0 or position `table_length`; that moment is its exit time. A removed object takes no further part in collisions. - Return the smallest integer that is greater than or equal to the largest exit time. ### Constraints - `1 <= n <= 2 * 10^5`, where `n = len(position) = len(velocity)` - `2 <= table_length <= 10^9` - Every `position[i]` is an integer with `0 < position[i] < table_length`, and all positions are distinct. - Every `velocity[i]` is an integer with `-10^9 <= velocity[i] <= 10^9` and `velocity[i] != 0`. - The answer is at most `10^9`, so it fits in a 32-bit signed integer. ### Examples **Example 1** ```text Input: position = [2, 4, 5], velocity = [2, -2, 4], table_length = 9 Output: 4 ``` The objects starting at 2 and 4 meet at position 3 at time 0.5 and exchange velocities. The first then moves left from 3 at speed 2 and leaves at time 2; the second moves right from 3 at speed 2 and leaves at time 3.5. The object starting at 5 moves right at speed 4, never meets another object, and leaves at time 1. The last exit is at time 3.5, so the answer is 4. **Example 2** ```text Input: position = [2, 5], velocity = [3, 1], table_length = 10 Output: 5 ``` The object starting at 2 catches up with the object starting at 5 at position 6.5 at time 1.5, and they exchange velocities. The front object now moves right at speed 3 and leaves at time `1.5 + 3.5 / 3`, about 2.67; the rear object now moves right at speed 1 and leaves at time `1.5 + 3.5 = 5`. The last exit time is exactly 5, so the answer is 5. **Example 3** ```text Input: position = [1], velocity = [-1000000000], table_length = 2 Output: 1 ``` The only object reaches position 0 at time `1 / 10^9`, which rounds up to 1.