Last Truck to Leave a One-Dimensional Lane

Problem Statement

A single-lane road segment is represented as a line segment from 0 to lane_length. There are n trucks on this road, each starting at a distinct coordinate. All trucks move at a constant speed of 1 unit per second.

Each truck i (for 0 <= i < n) has:

• An initial position positions[i] (0 < positions[i] < lane_length)
• A direction directions[i], which is either 'L' (moving towards 0) or 'R' (moving towards lane_length)

When two trucks meet at the same coordinate, they instantly bounce off each other and reverse their directions without losing speed. When a truck reaches coordinate 0 or coordinate lane_length, it immediately exits the lane.

Return a tuple or pair (exit_time, truck_id) representing the time the last truck leaves the road and the original 0-based index of that truck. If multiple trucks exit at the maximum exit time, return the one with the smaller truck_id.

Function Signature

def last_truck_to_exit(lane_length: int, positions: list[int], directions: str) -> tuple[int, int]:
    pass

Input Format

• lane_length: an integer representing the length of the lane.
• positions: a list of distinct integers representing the starting positions of the trucks.
• directions: a string of length n containing only 'L' and 'R', where directions[i] is the initial direction of truck i.

Output Format

• A tuple (exit_time, truck_id) where exit_time is the time the last truck leaves the lane, and truck_id is the original index of that truck.

Constraints

• 1 <= lane_length <= 10^9
• 1 <= n <= 10^5, where n = len(positions) = len(directions)
• 0 < positions[i] < lane_length
• All values in positions are pairwise distinct.
• directions[i] in {'L', 'R'}

Examples

Example 1

lane_length = 10
positions = [3, 7]
directions = "RL"

# Output: (7, 0)

Explanation:

• At t = 0, Truck 0 is at 3 moving right, and Truck 1 is at 7 moving left.
• At t = 2, they collide at position 5. Truck 0 reverses to moving left, and Truck 1 reverses to moving right.
• At t = 5, Truck 1 exits at 10 (having traveled from 5 to 10 in 3 seconds, total time 2 + 3 = 5).
• At t = 7, Truck 0 exits at 0 (having traveled from 5 to 0 in 5 seconds, total time 2 + 5 = 7).
• The last truck to exit is Truck 0 at time 7.

Example 2

lane_length = 8
positions = [2, 4, 6]
directions = "LRR"

# Output: (6, 1)

Explanation:

• Truck 0 moves left and exits at 0 at t = 2 without any collision.
• Truck 1 and Truck 2 both move right; neither collides.
• Truck 2 exits at 8 at t = 8 - 6 = 2.
• Truck 1 exits at 8 at t = 8 - 4 = 4... wait: Truck 1 starts at 4 and exits at 8 at time 8 - 4 = 4? Here max time is 4 for Truck 1. Output is (4, 1).