AcWing 908. 最大不相交区间数量
原题链接
简单
作者:
玛卡巴卡呀
,
2021-04-01 21:15:05
,
所有人可见
,
阅读 332
package tanxin;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
class Pairmax implements Comparable<Pairmax>{
int x;
int y;
public Pairmax(int x, int y) {
super();
this.x = x;
this.y = y;
}
@Override
public int compareTo(Pairmax p) {
// TODO Auto-generated method stub
return this.y-p.y>0?1:-1;
}
}
public class 最大不相交区间数量 {
/**
* @param args
* @throws IOException
*/
public static void main(String[] args) throws IOException {
// TODO Auto-generated method stub
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
int n=Integer.parseInt(bufferedReader.readLine());
Pairmax x[]=new Pairmax[n];
for(int i=0;i<n;i++){
String p[]=bufferedReader.readLine().split(" ");
int a=Integer.parseInt(p[0]);
int b=Integer.parseInt(p[1]);
x[i]=new Pairmax(a, b);
}
Arrays.sort(x);
int res=0;
int L=Integer.MIN_VALUE;
int R=Integer.MIN_VALUE;
for(int i=0;i<n;i++){
if(x[i].x > R){
R=x[i].y;
res++;
}
}
System.out.println(res);
}
}