P1697 [USACO18JAN] Lifeguards B

This problem is translated from deepseek-v3.

Farmer John has opened a swimming pool for his cows, thinking it will help them relax and produce more milk. To ensure safety, he hired $N$ cows as lifeguards, and each cow’s shift covers a continuous time interval during the day. For simplicity, the pool is open every day from time $t=0$ to time $t=1000$, so each shift can be described by two integers: the times when the cow starts and ends her shift. For example, a lifeguard working from time $t=4$ to time $t=7$ covers $3$ units of time (note that the endpoints represent time points). Unfortunately, Farmer John hired $1$ extra lifeguard beyond what his budget can support. Given that he must fire exactly $1$ lifeguard, what is the maximum total time that can be covered by the remaining lifeguards’ shifts? A time period is considered covered if at least one lifeguard is present.

The first line contains $N$ ($1 \leq N \leq 100$). The next $N$ lines each describe one lifeguard, using two integers in the range $0 \ldots 1000$ to represent the start and end times of that lifeguard’s shift. All endpoints are unique. Shifts from different lifeguards may overlap.

Output a single number: the maximum total time that can be covered by the remaining lifeguards’ shifts after Farmer John fires $1$ lifeguard.

Translated by ChatGPT 5