h290. 合并后的覆盖长度

题目描述

数轴上有 $n$ 个半开区间 $[l_i,r_i)$。求这些区间的并集总长度。

重叠或端点相接的区间可以合并。例如，$[1,3)$ 与 $[3,5)$ 合并后的覆盖长度为 $4$。

输入格式

第一行输入一个整数 $n$。

接下来 $n$ 行，每行输入两个整数 $l_i,r_i$。

输出格式

输出一个整数，表示并集总长度。

数据范围

• $1\le n\le 100000$
• $0\le l_i<r_i\le 10^9$

样例

4
1 5
3 7
10 12
12 15

11

标签：排序、区间合并