给定 N 个闭区间 [ai,bi]，请你将这些区间分成若干组，使得每组内部的区间两两之间（包括端点）没有交集，并使得组数尽可能小。
输出最小组数。
输入格式
第一行包含整数 N，表示区间数。
接下来 N 行，每行包含两个整数 ai,bi，表示一个区间的两个端点。
输出格式
输出一个整数，表示最小组数。
数据范围
1≤N≤105,
−109≤ai≤bi≤109
输入样例：
3
-1 1
2 4
3 5
输出样例：
2
图中的是C++的代码 所对应的java代码 在代码块里面
1、将所有区间按左端点从小到大排序
2、从前往后枚举每个区间，判断能否将其放到某个现有的组中，即是否存在当前区间的的左端点L > 任意组中右端点的最小值的组
如果不存在这样的组，则开新组，然后再将其放进组中
如果存在这样的组，则将其放在符合条件的组中，并更新当前组的右端点的值
3、为了不用每次选择组时都遍历所有组，可以通过小根堆来维护所有组中的尾端
证明：
1、按照上述存放，一定是一种合法的方案，则Ans <= cnt
2、由于分了cnt个组，则说明一定存在cnt个区间含有公共点，则一定至少开cnt个组，则Ans >= cnt
综合1、2可推出Ans == cnt
import java.util.*;
public class Main{
static int N = 100010;
static int n ;
static Node range[] = new Node[N];
public static void main(String [] args){
Scanner san = new Scanner(System.in);
n = san.nextInt();
for(int i = 0; i < n ; i++){
int a = san.nextInt();
int b = san.nextInt();
range[i] = new Node(a,b);
}
Arrays.sort(range,0,n,(o1,o2) -> o1.l-o2.l);
PriorityQueue minheap = new PriorityQueue<>();//通过小根堆来维护所有组中的尾端
for(int i = 0 ; i < n ;i++){
if(minheap.isEmpty() || minheap.peek() >= range[i].l)
minheap.add(range[i].r);
else{
minheap.poll();
minheap.add(range[i].r);
}
}
System.out.println(minheap.size());
}
static class Node{
int l ;
int r ;
public Node(int l , int r){
this.l = l ;
this.r = r ;
}
}
}
这里面我把循环换成for(Node item : range) 就循环不了出现空指针异常 可能是无法转换过去 具体还在商榷
