【编程笔记】区间合并

给定 n 个区间 [l,r]，要求合并所有有交集的区间。

注意如果在端点处相交，也算有交集。

输出合并完成后的区间个数。

例如：[1,3] 和 [2,6] 可以合并为一个区间 [1,6]。

输入格式

第一行包含整数 n。

接下来 n 行，每行包含两个整数 l 和 r。

输出格式

共一行，包含一个整数，表示合并区间完成后的区间个数。

区间合并思路

首先，按区间左端点进行排序。

其次，依次判断是否存在交集。

对于判断交集而言，在排序之后，区间的关系有三种可能。

1.区间A包含了区间B。

2.区间A与区间B有交集。

3.区间A与区间B没有关系。

1.2.条件符合区间合并的要求，从中也可以得出比较的条件，即出区间A的右端点>=区间A的左端点（=是因为端点处相交，也算有交集）。

由于只需统计合并完成后的区间数量，因此需要先记录区间总数，每当合并的时候减一。

而为了提高效率，在判断完需要合并区间之后，直接更新接下要比较的区间，使之成为之前需要合并的区间。

比如，有区间A,B,C（左端点有序）。区间A和B判断完需要合并后，直接更新B，使B区间为原来A和B的合并区间，再将新的B区间和C比较。

这样一来，就可以快速统计需要合并区间的数量了。

sort 排序的是一给左闭右开的区间。 （即取得到最左边元素，但取不到最右边元素）

而对于sort(a+1, a+1+n)而言，覆盖的范围是a[1] - a[n]。

此外，a的效果等同于a[0]，所以a + 1就是a[1]，a + 1 + n就是a[n + 1]，因为sort左闭右开的特性，所以不取a[n + 1]，只取到a[n]。

至于这里的pair就是将两个变量关联在一起,可以认为是结构体,不过只有两个变量,而且pair排序的时候,优先第一位,这样可以快速实现区间左端点进行排序。

开心，这比离散化简单多了。