AcWing 803. 区间合并(Java版本)
原题链接
简单
作者:
恒心
,
2021-01-25 19:21:54
,
所有人可见
,
阅读 306
import java.io.*;
import java.util.*;
class Seg{
int L;
int R;
Seg(int l, int r){
this.L = l;
this.R = r;
}
}
class Main{
public static void main(String[] args) throws Exception{
Scanner sc = new Scanner(System.in);
ArrayList<Seg> list = new ArrayList<>();
int n = sc.nextInt();
for(int i = 0; i < n; ++i){
int L = sc.nextInt();
int R = sc.nextInt();
list.add(new Seg(L, R));
}
Collections.sort(list, new Comparator<Seg>(){
public int compare(Seg o1, Seg o2){
return o1.L - o2.L;
}
});
int st = Integer.MIN_VALUE, sd = Integer.MIN_VALUE;
ArrayList<Seg> res = new ArrayList<>();
for(Seg s : list){
if(sd < s.L){
if(st != Integer.MIN_VALUE){
res.add(new Seg(st, sd));
}
st = s.L;
sd = s.R;
}else{
sd = Math.max(sd, s.R);
}
}
if(st != Integer.MIN_VALUE){res.add(new Seg(st, sd));}
System.out.println(res.size());
}
}