AcWing 906. 区间分组java
原题链接
简单
作者:
huaqingren
,
2021-02-18 15:22:59
,
所有人可见
,
阅读 275
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;
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);
// for(int i=0;i<n;i++)
// System.out.println(nodes[i].l+" "+nodes[i].r);
//按照右端点从小到大排列
Queue<Node> queue=new PriorityQueue<Node>(cmp);
for(int i=0;i<n;i++)
{
Node t=nodes[i];
//如果当前小根堆没有元素或者存在交集,需要开辟一个新的分组
if(queue.isEmpty()||queue.peek().r>=t.l) queue.offer(t);
else
{
//否则直接加入一个最小的分组
queue.poll();
queue.offer(t);
}
}
System.out.println(queue.size());
scan.close();
}
private static class Node implements Comparable<Node>
{
private int l;
private int r;
public Node(int l,int r)
{
this.l=l;
this.r=r;
}
@Override
public int compareTo(Node o)
{
//按照左端点从小到大排序
return this.l-o.l;
}
}
}