Count players reaching end with moving watchers

Problem Statement

You are monitoring a single-lane race of length L. There are N players starting at position 0, attempting to reach position L. There are M "watchers" moving along the lane. Each watcher i is defined by a range [start_i, end_i] and moves back and forth between these boundaries at a constant speed of 1 unit per time step. A watcher starts at start_i at time t=0 and reaches end_i at time t = end_i - start_i, then turns around.

A player is "seen" if they are at position x at time t such that a watcher is also at position x at time t. Assume players move at a constant speed of 1 unit per time step (i.e., a player at position x at time t is at position x + 1 at time t + 1).

Given the total length L and a list of watcher start/end bounds, return the number of players who can reach position L without ever being at the same position as a watcher at the same time. Assume players can start at position 0 at any integer time t >= 0.

Function Signature

def count_safe_players(L: int, watchers: List[Tuple[int, int]]) -> int:

Examples

Example 1: Input: L = 5, watchers = [(1, 3)] Output: 4 Explanation: A player starting at t=0 reaches position 1 at t=1. The watcher is at 1 at t=0, 2 at t=1, and 3 at t=2. The player avoids the watcher by choosing the correct start time.

Constraints

• 1 <= L <= 10^5
• 1 <= M <= 10^3
• All inputs are integers.

Edge Cases

• Watchers with range [x, x] (stationary).
• L is very small compared to the number of watchers.