题目
某校大门外长度为L的马路上有一排树，每两棵相邻的树之间的间隔都是1米。我们可以把马路看成一个数轴，马路的一端在数轴0的位置，另一端在L的位置；数轴上的每个整数点，即0，1，2，……，L，都种有一棵树。
由于马路上有一些区域要用来建地铁。这些区域用它们在数轴上的起始点和终止点表示。已知任一区域的起始点和终止点的坐标都是整数，区域之间可能有重合的部分。现在要把这些区域中的树（包括区域端点处的两棵树）移走。你的任务是计算将这些树都移走后，马路上还有多少棵树。
想法
刚开始，我想通过判断相邻区间的右端点和左端点，来确定是否相交。但是提交，总是有几个测试点通不过。
然后，通过看别人的思路，我看到了一个非常简单的思路。可能是我把问题想得太复杂了。
就我知道而言该题有三种做法：
- 数组标记法(刚开始我怕超时)
- 端点判断法
- 线段树
代码
数组标记法
#include<iostream>
using namespace std;
int main(){
int a[10010];
int L,M;
int i,j;
int sum = 0;
cin>>L>>M;
for(int i=0;i<=L;i++){
a[i] = 0;
}
while(M--){
cin>>i>>j;
for(int k = i;k<=j;k++){
if(a[k] == 0)a[k] = 1;
//若该树要被移走，就标记为1
}
}
for(int i = 0;i<=L;i++){
if(a[i] == 0)sum++;
}
cout<<sum<<endl;
return 0;
}
端点判断法
#include<iostream>
#include<algorithm>
using namespace std;
int L,M;
int nStart,nEnd;
int sum = 0;
int q=1;
struct node{
int l;
int r;
}Section[101];
int mySort(node x, node y){
return x.l < y.l;
}
int main(){
cin>>L>>M;
//赋值
for(int i=1;i<=M;i++){
cin>>nStart>>nEnd;
Section[i].l = nStart;
Section[i].r = nEnd;
}
//排序
sort(Section+1,Section+M+1,mySort);
//如果前面区间的右端点小于后面区间的左端点，则相交
//如果前面区间的右端点大于后面区间的右端点，则重合
//下面为构造新区间，将合并重合的组成一个新区间
for(int i=2;i<=M;i++){
if(Section[i].l > Section[q].r)Section[++q] = Section[i];
else Section[q].r = max(Section[q].r , Section[i].r);
}
for(int i = 1;i<=q;i++){
sum += Section[i].r - Section[i].l+1;
}
cout<<L-sum+1<<endl;
return 0;
}