AcWing 422. 校门外的树Java详细注释
原题链接
简单
作者:
长街听风
,
2021-01-24 16:51:32
,
所有人可见
,
阅读 305
Java 代码
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int L = scanner.nextInt();//树从0-L,故共有L+1棵树
int M = scanner.nextInt();
List<int[]> list = new ArrayList<>();//用于存储每段区间
for(int i = 0 ;i < M;i++){
int[] segment = {scanner.nextInt(),scanner.nextInt()};
list.add(segment);
}
list.sort(new Comparator<int[]>() {//按照每段区间的左端点由小到大排序
@Override
public int compare(int[] o1, int[] o2) {
return o1[0] - o2[0];
}
});
//最开始的基准区间
int start = list.get(0)[0];
int end = list.get(0)[1];
int res = L + 1;//原始树的数量
for(int i = 1;i < list.size();i++){
if(list.get(i)[0] <= end){//当前区间左端点在基准区间内,说明两个区间有重合部分
end = Math.max(list.get(i)[1],end);//更新基准区间的右端点为两个区间右端点较大的那个
}else{//当前区间与基准区间无重合部分,说明第一段基准区间合并结束,更新当前区间为新基准区间
//让结果减去上个区间所包含的树的数量(即res = res-(end - start +1))
res -= end - start +1;
start = list.get(i)[0];
end = list.get(i)[1];
}
}
res -= end - start + 1;//减去最后一段合并的基准区间包含的树的数量
System.out.println(res);
}
}