AcWing 905. 区间选点
原题链接
简单
作者:
季之秋
,
2021-02-20 16:47:45
,
所有人可见
,
阅读 183
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
Pair arr[]=new Pair[100010];
int n=sc.nextInt();
for(int i=0;i<n;i++){
arr[i]=new Pair(sc.nextInt(),sc.nextInt()); //输入区间
}
Arrays.sort(arr,0, n,(o1, o2) -> o1.r - o2.r); //按右端点r排序
int res=0,ed=Integer.MIN_VALUE; //ed负无穷
for(int i=0;i<n;i++){
if(arr[i].l>ed){ //没有被选中就是上个区间右端点在下个区间左端点左边
res++; //新建一个点
ed=arr[i].r; //这个点为当前区间的右端点
}
}
System.out.println(res);
}
static class Pair{
int l,r;
Pair(int l,int r){
this.l=l;
this.r=r;
}
}
}