区间合并
给定 n 个区间 [li,ri]，要求合并所有有交集的区间。
注意如果在端点处相交，也算有交集。
输出合并完成后的区间个数。
例如：[1,3] 和 [2,6] 可以合并为一个区间[1,6]。
输入格式
第一行包含整数 n。
接下来 n 行，每行包含两个整数 l 和 r。
输出格式
共一行，包含一个整数，表示合并区间完成后的区间个数。
数据范围
1≤n≤100000,
−109≤li≤ri≤109
输入样例：
5
1 2
2 4
5 6
7 8
7 9
输出样例：
3
题目的意思比较简单，就是有一些区间，给你他的起始点和终止点，让你将遇到的小区间合并成一个大区间，并最终返回大区间的个数。
思路一般是先将这些起始点和终点按照起始点有小到大排序，如果遇到起始点相同的，就排序他的终点，终点也是有小到大进行排序，这样可以省去一些麻烦。
思路比较简单，但是实现起来有一些细节要注意一下：
算了，先上代码：
#include
using namespace std ;
const int N = 100010 ;
struct region
{
int start ;
int end ;
} re[N];
int main()
{
int n ;
cin >> n ;
for(int i = 1 ; i <= n ; ++ i )
{
cin >> re[i].start >> re[i].end ;
}
sort(re + 1 , re + n + 1 , [] (region x , region y)
{
if(x.start == y.start)
{
return x.end < y.end ;
}
return x.start < y.start ;
}) ;
re[n+1].start = re[n].end + 1 ; //个人觉得比较妙的一步，他直接限制了下面的for循环必须是if结尾的，就省去了一些麻烦
int start = re[1].start ;
int end = re[1].end ;
int num = 1 ;
for(int i = 2 ; i <= n + 1 ; ++ i)
{
if(re[i].start > end)
{
num ++ ;
start = re[i].start ;
end = re[i].end ;
}
else
{
end = max(end , re[i].end) ;
}
}
cout << num << endl ;
return 0;
}
同理，我们再来看与她极其相似的一道题
校门外的树
某校大门外长度为 L 的马路上有一排树，每两棵相邻的树之间的间隔都是 1 米。
我们可以把马路看成一个数轴，马路的一端在数轴 0 的位置，另一端在 L 的位置；数轴上的每个整数点，即0，1，2，……，L，都种有一棵树。
由于马路上有一些区域要用来建地铁。
这些区域用它们在数轴上的起始点和终止点表示。
已知任一区域的起始点和终止点的坐标都是整数，区域之间可能有重合的部分。
现在要把这些区域中的树（包括区域端点处的两棵树）移走。
你的任务是计算将这些树都移走后，马路上还有多少棵树。
输入格式
输入文件的第一行有两个整数 L和 M，L 代表马路的长度，M 代表区域的数目，L 和 M 之间用一个空格隔开。
接下来的 M 行每行包含两个不同的整数，用一个空格隔开，表示一个区域的起始点和终止点的坐标。
输出格式
输出文件包括一行，这一行只包含一个整数，表示马路上剩余的树的数目。
数据范围
1≤L≤10000,
1≤M≤100
输入样例：
500 3
150 300
100 200
470 471
输出样例：
298
这一题我一开始没仔细看题目，就直接盯着样例看了老半天。
我一开始想的是，这一共500棵树，我怎么算都是297呀，为什么是298呢？？？
原来是，0-500…….哈哈，那没事了。
所以一共是501棵树。
思路与上题几乎一样
#include
using namespace std ;
const int N = 110 ;
struct region
{
int start ;
int end ;
} re[N];
int main()
{
int n , m ;
cin >> n >> m ;
n ++ ;
for(int i = 1 ; i <= m ; ++ i)
{
cin >> re[i].start >> re[i].end ;
}
sort(re + 1 , re + 1 + m , [] (region x , region y)
{
if(x.start == y.start)
{
return x.end < y.end ;
}
return x.start < y.start ;
}) ;
re[m+1].start = 10001 ; //将x
int start = re[1].start ;
int end = re[1].end ;
int res = 0 ;
for(int i = 2 ; i <= m + 1 ; ++ i)
{
if(re[i].start > end)
{
res += (end - start + 1) ;
start = re[i].start ;
end = re[i].end ;
}
else
{
end = max(end , re[i].end) ;
}
}
cout << n - res << endl ;
return 0 ;
}
