目录
一般要求
给定 n 个区间
，要求合并所有有交集的区间。
注意如果在端点处相交，也算有交集。
例如：[1,3] 和 [2,6] 可以合并为一个区间 [1,6]。
[1,6] 和 [2,3] 可以合并为一个区间 [1,6]。
[1,3] 和 [5,6] 就不能合并为一个区间。
解决方法
区间合并问题一般就是按照某个区间的左端点或者右端点排序。
如果按照左端点排序，一般就是根据上一个区间的右端点和当前区间的左端点进行比较，看是否能够合并，如果两个区间是分开的，那就不能合并。
这个题主要就是注意一下细节问题。
// 伪代码：
PriorityQueue q // 我这里定义了一个优先队列，存储所有的区间，为的是直接给左端点排序，也可以用sort
start = -10e9 // 记录区间的左端点
end = -10e9 // 记录区间的右端点
while( q 不空）{
l , r = 取出队头的两个元素（左端点和右端点）
if（ l > start ）更新start和end为当前区间的值; // 说明是第一个区间 或者 是该区间与上个区间没有相交的部分
else end = max ( end , r ) // 否则就合并两个区间，右端点取最大值 ，因为两个区间有可能相交，也有可能一个区间被另一个区间覆盖
}
题目
给定 n 个区间
注意如果在端点处相交，也算有交集。
输出合并完成后的区间个数。
例如：[1,3] 和 [2,6] 可以合并为一个区间 [1,6]。
输入格式
第一行包含整数 n。
接下来 n 行，每行包含两个整数 l 和 r。
输出格式
共一行，包含一个整数，表示合并区间完成后的区间个数。
数据范围
1≤n≤100000,
−10^9≤li≤ri≤10^9输入样例：
5 1 2 2 4 5 6 7 8 7 9输出样例：
3
import java.io.*;
import java.util.*;
class Main{
static int N = 100010;
static int n;
static List<PII> l = new ArrayList<>();
public static void main(String[] args) throws IOException{
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(in.readLine());
for(int i=0;i<n;i++){
String[] str = in.readLine().split(" ");
l.add(new PII(Integer.parseInt(str[0]),Integer.parseInt(str[1])));
}
Collections.sort(l); // 排序
// 进行区间合并
int begin = (int)-10e9;
int end = (int)-10e9;
int res = 0;
for(PII i: l){
if(i.l>end){
begin=i.l;
end = i.r;
res++;
}
else{
end = Math.max(end,i.r);
}
}
System.out.println(res);
}
}
class PII implements Comparable<PII>{ // 存储区间，并实现排序方法
int l;
int r;
public PII(int l,int r){
this.l = l;
this.r = r;
}
public int compareTo(PII p){
return Integer.compare(l,p.l);
}
}
