AcWing 422. 校门外的树 Java
原题链接
简单
作者:
天乔巴夏丶
,
2021-01-16 14:41:12
,
所有人可见
,
阅读 325
import java.util.*;
class Main{
static int l, m;
static int[][] nums;
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
l = sc.nextInt();
m = sc.nextInt();
nums = new int[m][2];
for(int i = 0; i < m; i ++){
nums[i][0] = sc.nextInt();
nums[i][1] = sc.nextInt();
}
// 按左端点排序
Arrays.sort(nums, (o1 , o2)-> o1[0] - o2[0]);
int cnt = 0; // 表示减去的树个数
int begin = nums[0][0] , end = nums[0][1];
for(int i = 1; i < m; i ++){
if(nums[i][0] <= end){
// 更新end 为 两个end的最大值
end = Math.max(nums[i][1], end);
}else{
cnt += (end - begin + 1);
// 更新两个端点
begin = nums[i][0];
end = nums[i][1];
}
}
int n = end - begin + 1; // 最后一个区间
System.out.println(l + 1 - cnt - n);
}
}