QOJ.ac

QOJ

Time Limit: 3 s Memory Limit: 512 MB Total points: 100

# 6178. 区间子集问题

统计

给定实轴上 $n$ 个区间,第 $i$ 个区间为 $[L_i, R_i]$ ($1 \leq i \leq n$)。这 $n$ 个区间的 $2n$ 个区间端点互不相同。由此可知,这 $n$ 个区间中,任何 $2$ 个区间或其交集为空,或有包含关系。

区间子集问题:对于实轴上给定的区间端点互不相同的 $n$ 个区间 $[L_i , R_i ]$ ($1 \leq i \leq n$),从每个子区间 $[L_i, R_i]$ 中选取一个子区间 $[l_i, r_i]$ ($L_i \leq l_i < r_i \leq R_i$),使得选出的任何 $2$ 子区间的交集最多只有 $1$ 个点。要求选出的 $n$ 个子区间的长度之和 $\sum_{i=1}^n (r_i-l_i)$ 达到最大。

输入格式

第一行为一个正整数 $n$。

接下来每行有两个整数,第 $i + 1$ 行给出两个整数 $L_i, R_i$,表示相应区间为 $[L_i, R_i]$。

输出格式

输出计算出的最大子区间的长度和。

样例数据

样例输入

4
1 10
2 3
5 9
6 7

样例输出

7

子任务

测试数据中 $10\%$ 的数据满足 $n \leq 10$ 。

测试数据中 $40\%$ 的数据满足 $n \leq 500$ 。

测试数据中 $100\%$ 的数据满足 $n \leq 2\,000$ 。