908. 区间合并
时间限制：1000 MS 内存限制：64 MB
题目描述
# 区间合并 ## 题目描述 给定 $n$ 个闭区间 $[l_i,r_i]$，请合并所有有交集的区间，直到剩余区间两两没有交集，并输出合并后的区间个数。 如果两个区间仅在端点处相交，也需要合并。例如，$[1,2]$ 和 $[2,4]$ 应合并为 $[1,4]$。 例如，$[1,3]$ 和 $[2,6]$ 可以合并为一个区间 $[1,6]$。 ## 输入格式 从文件 `merges.in` 中读入数据。 第一行包含一个整数 $n$，表示区间个数。 接下来 $n$ 行，每行包含两个整数 $l_i$ 和 $r_i$，表示一个闭区间 $[l_i,r_i]$。 ## 输出格式 将结果输出到文件 `merges.out` 中。 输出一行，包含一个整数，表示合并后的区间个数。 ## 数据范围 - $1 \le n \le 100000$。 - $-10^9 \le l_i \le r_i \le 10^9$。 ## 样例输入 ``` 5 1 2 2 4 5 6 7 8 7 9 ``` ## 样例输出 ``` 3 ``` ## 样例说明 合并后得到三个区间：$[1,4]$、$[5,6]$ 和 $[7,9]$。 ## 资源限制 - 时间限制：$1000$ 毫秒。 - 内存限制：$64$ MB。