AcWing 905. 区间选点java
原题链接
简单
作者:
huaqingren
,
2021-02-17 21:37:54
,
所有人可见
,
阅读 248
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;
public class Main
{
static Comparator<Node> cmp=new Comparator<Node>()
{
//按照右端点从小到大排序
@Override
public int compare(Node o1, Node o2)
{
return o1.r-o2.r;
}
};
public static void main(String[] args)
{
Scanner scan=new Scanner(System.in);
int n=scan.nextInt();
Node[] nodes=new Node[n];
for(int i=0;i<n;i++)
{
int l=scan.nextInt();
int r=scan.nextInt();
nodes[i]=new Node(l,r);
}
Arrays.sort(nodes,cmp);
int cnt=0,ed=-2000000000;
for(int i=0;i<n;i++)
{
if(nodes[i].l>ed)
{
cnt++;
ed=nodes[i].r;
}
}
System.out.println(cnt);
scan.close();
}
private static class Node
{
private int l;
private int r;
public Node(int l,int r)
{
this.l=l;
this.r=r;
}
}
}