AcWing 803. 区间合并-java版,有注释
原题链接
简单
作者:
OneDay1
,
2021-02-12 21:49:06
,
所有人可见
,
阅读 281
import java.util.*;
public class Main{
static int[] a;
static int N = 100010;
static ArrayList<int[]> save = new ArrayList<>();
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
for(int i = 0;i < n; i++){
a = new int[2];
a[0] = sc.nextInt();
a[1] = sc.nextInt();
save.add(a);
}
// 自定义排序方式
save.sort(new Comparator<int[]>(){
// 重写规则:o1大于o2时,返回正整数(1);反之返回负整数(-1),相等返回0。与compareTo的重写规则相同。
@Override
public int compare(int[] o1,int[] o2){
//如果传递的参数是第一个是o1,第二个是o2,比较的时候也是用o1-o2进行比较,那么就是升序
return o1[0] - o2[0];
}
});
int count = 0;
// 假设维护的右端点为r
int r = Integer.MIN_VALUE;
for(int a[]:save){
// 如果第二个区间的左边大于r(维护区间的右端点);表示两者没有交集,则所求区间个数+1;
if(a[0] > r) count++;
// 第二个区间的左边小于或者等于r(维护区间的右端点),也就是两者区间存在包含和交集,那么更新维护的区间长度
r = Math.max(r,a[1]);
}
System.out.println(count);
}
}