Hall - MarisaOJ: Marisa Online Judge

Hall

Time limit: 1000 ms
Memory limit: 256 MB
You are managing a hall. There are $n$ registration requests to use the hall, the $i$-th request is $[l_i, r_i]$, requesting to use the hall from time $l_i$ to $r_i$, with the total usage time being $r_i - l_i + 1$. At any given time, only one request can be accepted. For example, two requests $[3, 5]$ and $[5, 7]$ cannot be accommodated simultaneously due to the overlap at time $5$. Your task is to select a subset of registration requests such that no two requests overlap in time and the total usage time of the hall is maximized. ### Input - The first line contains an integer $n$. - The next $n$ lines each contain two integers $l_i$ and $r_i$. ### Output - Output a single integer representing the maximum total usage time of the hall. ### Constraints - $1 \le n \le 10^5$ - $1 \le l_i, r_i \le 10^5$ ### Example Input: ``` 4 1 3 2 5 4 6 6 8 ``` Output: ``` 7 ``` Explanation: Choose $[2,5]$ and $[6,8]$.