Calculate Highway Tolls from Ordered Checkpoint Logs

Problem Statement

A regional transportation department operates an automated tolling system along a single linear highway. Vehicles are tracked via sensors installed at designated checkpoints along the road. Each checkpoint corresponds to a specific mile marker.

You are given a chronological list of sensor logs recorded over a single day. Each log entry indicates the time a vehicle was observed at a specific checkpoint. Because sensor logs arrive in chronological order across the entire highway, records for different vehicles are interleaved.

Every consecutive pair of checkpoint sightings for the same vehicle constitutes a billable segment. The toll for a segment is calculated as:

segment_toll = abs(curr_checkpoint_mile - prev_checkpoint_mile) * rate_per_mile

Calculate the total toll collected across all vehicles for the day according to the following rules:

• Each vehicle is billed for every consecutive recorded segment individually. Net displacement is not used; reversing direction or repeating checkpoints does not offset or cancel previous charges.
• If a vehicle visits the same checkpoint consecutively (e.g., stopping or lingering), the distance is 0 and incurs no additional toll.
• If a vehicle is only recorded once during the day, it has not completed any segment and incurs no toll.

Function Signature

def calculate_total_toll(
    logs: list[tuple[int, str, str]],
    checkpoint_distances: dict[str, int],
    rate_per_mile: int,
) -> int:
    pass

Parameters

• logs: A list of tuples (timestamp, vehicle_id, checkpoint_id) sorted in ascending order of timestamp (timestamp >= 0).
• checkpoint_distances: A dictionary mapping each checkpoint_id (string) to its position along the highway in miles (non-negative integer).
• rate_per_mile: An integer representing the cost in cents per mile traveled.

Returns

• An integer representing the total toll amount in cents collected across all vehicles.

Constraints

• 0 <= len(logs) <= 100,000
• 1 <= len(checkpoint_distances) <= 1,000
• 1 <= rate_per_mile <= 100
• All checkpoint_id entries in logs are guaranteed to exist in checkpoint_distances.
• timestamp is a strictly increasing or non-decreasing integer.
• vehicle_id is a non-empty alphanumeric string.

Examples

Example 1

logs = [
    (100, "CAR_A", "CP_1"),
    (110, "CAR_B", "CP_2"),
    (130, "CAR_A", "CP_3"),
    (150, "CAR_B", "CP_1"),
    (180, "CAR_A", "CP_1"),
]
checkpoint_distances = {
    "CP_1": 10,
    "CP_2": 25,
    "CP_3": 40,
}
rate_per_mile = 2

# CAR_A segments:
#   CP_1 (10) -> CP_3 (40): distance = |40 - 10| = 30 miles -> 30 * 2 = 60 cents
#   CP_3 (40) -> CP_1 (10): distance = |10 - 40| = 30 miles -> 30 * 2 = 60 cents
#   CAR_A subtotal = 120 cents
#
# CAR_B segments:
#   CP_2 (25) -> CP_1 (10): distance = |10 - 25| = 15 miles -> 15 * 2 = 30 cents
#   CAR_B subtotal = 30 cents
#
# Total = 120 + 30 = 150 cents
assert calculate_total_toll(logs, checkpoint_distances, rate_per_mile) == 150

Example 2

logs = [
    (10, "CAR_X", "CP_1"),
    (20, "CAR_Y", "CP_2"),
    (30, "CAR_X", "CP_1"),
]
checkpoint_distances = {
    "CP_1": 5,
    "CP_2": 15,
}
rate_per_mile = 5

# CAR_X: CP_1 -> CP_1: distance = |5 - 5| = 0 miles -> 0 cents
# CAR_Y: only 1 log -> 0 cents
assert calculate_total_toll(logs, checkpoint_distances, rate_per_mile) == 0

Edge Cases

• Empty logs list should return 0.
• Vehicles with only one recorded checkpoint produce no completed segment.
• Checkpoint repeated back-to-back produces distance 0.