题目描述
某校大门外长度为L的马路上有一排树,每两棵相邻的树之间的间隔都是1米。
我们可以把马路看成一个数轴,马路的一端在数轴0的位置,另一端在L的位置;数轴上的每个整数点,即0,1,2,……,L,都种有一棵树。
由于马路上有一些区域要用来建地铁。
这些区域用它们在数轴上的起始点和终止点表示。
已知任一区域的起始点和终止点的坐标都是整数,区域之间可能有重合的部分。
现在要把这些区域中的树(包括区域端点处的两棵树)移走。
你的任务是计算将这些树都移走后,马路上还有多少棵树。
样例
输入样例:
500 3
150 300
100 200
470 471
输出样例:
298
算法
(区间合并) $O(m)$
java 代码
import java.io.*;
import java.util.*;
class Main{
static final int N = 10010;
static int[][] way = new int[N][2];
public static void main(String[] args) throws IOException{
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
int n,m;
String[] in=bf.readLine().split(" ");
n=Integer.parseInt(in[0]);
m=Integer.parseInt(in[1]);
for(int i=0;i<m;++i){
in=bf.readLine().split(" ");
way[i][0]=Integer.parseInt(in[0]);
way[i][1]=Integer.parseInt(in[1]);
}
Arrays.sort(way,0,m,(t1,t2)->Integer.compare(t1[0],t2[0]));
// 区间合并
int f=way[0][0],t=way[0][1],res=f;// 第一条路前的树
for(int i=1;i<m;++i){
if(way[i][0]-t<=1)// 后面一条路的起点与前面的终点相距不超过1就能合并
t=Math.max(t,way[i][1]);
else{
f=way[i][0];
res+=f-t-1;
t=way[i][1];
}
}
res+=n-t;// 最后一条路后的树
System.out.println(res);
bf.close();
}
}