Problem5702--区间覆盖

5702: 区间覆盖

Time Limit: 1.000 Sec  Memory Limit: 256 MB
Submit: 13  Solved: 9
[Submit] [Status] [Web Board] [Creator:]

Description

你有N个左闭右开区间,你现在想要把其中有重叠的区间合并在一起。

若两个区间有相同部分落在数轴上,认为他们有重叠部分,则需要合并。

例如区间[1,3)和[2,6),你可以合并为一个新的区间[1,6)。

例如区间[1,3)和[4,6),由于两者没有重叠部分,所以无法合并。

特别地,如果有区间[1,3)和[3,6),也可以合并成为[1,6)。

现在请你计算,在完成所有可以合并的区间后,求出剩余的独立区间的总长度。


Input

第一行包含一个正整数n,表示区间的数量。

接下来n行,每行包含两个整数li和ri,表示一个左闭右开的区间[li,ri)


Output

输出一个整数,表示经过合并后,剩余的独立区间的总长度。

Sample Input

3
1 5
2 4
6 8

Sample Output

6

HINT

【数据范围】

50%的数据$1 \le N \le 1000$

100%的数据$1 \le N \le 10^5,-10^9 \le l_i,r_i \le 10^9$

说明:输入的区间可能有li==ri的情况,此时视为空区间,长度为0。

且输入的区间不会出现li>ri的情况。

Source/Category

 

[Submit] [Status]