Minimize Car Removals for a Two-Car Bridge

A freight rail company operates a one-way bridge that can support at most two train cars simultaneously. To ensure bridge safety, two conditions must be met:

1. Every individual car crossing the bridge must have a weight less than or equal to limit.
2. Every adjacent pair of cars crossing the bridge together must have a combined weight less than or equal to limit.

You are given an array of positive integers weights, representing the weights of cars in the order they arrive at the bridge, and an integer limit representing the maximum weight capacity of the bridge.

You may remove cars from anywhere in the queue, but you cannot reorder the remaining cars. Return the minimum number of cars that must be removed so that the retained cars safely cross the bridge.

Function Signature

def min_car_removals(weights: list[int], limit: int) -> int:
    pass

Input and Output Format

• Input:
  • weights: A list of integers where weights[i] is the weight of the i-th car.
  • limit: An integer representing the bridge capacity.
• Output: An integer denoting the minimum number of cars removed.

Constraints

• 1 <= len(weights) <= 200,000
• 1 <= weights[i] <= 10^9
• 1 <= limit <= 10^9

Examples

Example 1

weights = [5, 6, 2, 3, 7]
limit = 8

Output: 2

Explanation:

• If we remove cars with weights 6 and 7, the retained queue is [5, 2, 3].
• Each individual weight is <= 8 (5 <= 8, 2 <= 8, 3 <= 8).
• Each adjacent pair sum is <= 8 (5 + 2 = 7 <= 8, 2 + 3 = 5 <= 8).
• The minimum number of removals is 5 - 3 = 2.

Example 2

weights = [9, 10, 4, 5, 2]
limit = 7

Output: 3

Explanation:

• Cars 9 and 10 individually exceed limit and must be removed.
• From [4, 5, 2], keeping both 4 and 5 is invalid because 4 + 5 = 9 > 7.
• We can keep [4, 2] (or [5, 2]), which has length 2.
• Total cars removed: 5 - 2 = 3.

Edge Cases

• All cars exceed limit: all cars must be removed; output is len(weights).
• All adjacent pairs already satisfy w[i] + w[i+1] <= limit: 0 removals needed.
• Only one car can be safely kept across the entire sequence.