AcWing 905. 区间选点
原题链接
简单
作者:
JAVA小老弟
,
2020-02-03 14:06:40
,
所有人可见
,
阅读 575
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Comparator;
import java.util.PriorityQueue;
public class Main{
public static void main(String[] args) throws IOException {
//用一个优先队列去记录 排序方式为end从小到大
PriorityQueue<Node> res=new PriorityQueue<>(new Comparator<Node>() {
@Override
public int compare(Node o1, Node o2) {
return o1.end-o2.end;
}
});
BufferedReader r=new BufferedReader(new InputStreamReader(System.in));
String s[]=r.readLine().split(" ");
int N=Integer.parseInt(s[0]);
for (int i = 0; i <N ; i++) {
String line[]=r.readLine().split(" ");
int a=Integer.parseInt(line[0]);
int b=Integer.parseInt(line[1]);
res.add(new Node(a,b));
}
//最起码有一个
int cnt=1;
//第一个结点的end作为终点
int end=res.poll().end;
for (int i = 1; i <N ; i++) {
Node tp=res.poll();
if(tp.begin>end){
//如果弹出的元素begin>end 说明没有交集 cnt++ 更新end
cnt+=1;
end=tp.end;
}
}
System.out.println(cnt);
}
}
class Node{
//结点记录begin 和end坐标
int begin;
int end;
public Node(int x,int y){
begin=x;
end=y;
}
}