#PQJ1193x6178. QOJ 1193_6178
QOJ 1193_6178
给定实轴上 𝑛 个区间,第 𝑖 个区间为 [ 𝐿 𝑖 , 𝑅 𝑖 ] ( 1 ≤ 𝑖 ≤ 𝑛 )。这 𝑛 个区间的 2 𝑛 个区间端点互不相同。由此可知,这 𝑛 个区间中,任何 2 个区间或其交集为空,或有包含关系。
区间子集问题:对于实轴上给定的区间端点互不相同的 𝑛 个区间 [ 𝐿 𝑖 , 𝑅 𝑖 ] ( 1 ≤ 𝑖 ≤ 𝑛 ),从每个子区间 [ 𝐿 𝑖 , 𝑅 𝑖 ] 中选取一个子区间 [ 𝑙 𝑖 , 𝑟 𝑖 ] ( 𝐿 𝑖 ≤ 𝑙 𝑖 < 𝑟 𝑖 ≤ 𝑅 𝑖 ),使得选出的任何 2 子区间的交集最多只有 1 个点。要求选出的 𝑛 个子区间的长度之和 ∑ 𝑖
1 𝑛 ( 𝑟 𝑖 − 𝑙 𝑖 ) 达到最大。
输入格式
第一行为一个正整数 𝑛 。
接下来每行有两个整数,第 𝑖 + 1 行给出两个整数 𝐿 𝑖 , 𝑅 𝑖 ,表示相应区间为 [ 𝐿 𝑖 , 𝑅 𝑖 ] 。
输出格式
输出计算出的最大子区间的长度和。
样例数据 样例输入 4 1 10 2 3 5 9 6 7 样例输出 7 子任务
测试数据中 10 % 的数据满足 𝑛 ≤ 10 。
测试数据中 40 % 的数据满足 𝑛 ≤ 500 。
测试数据中 100 % 的数据满足 𝑛 ≤ 2 000 。