题目描述
给定 n 个区间 [li,ri]
,要求合并所有有交集的区间。
注意如果在端点处相交,也算有交集。
输出合并完成后的区间个数。
例如:[1,3]和[2,6]可以合并为一个区间[1,6]。
样例
5
1 2
2 4
5 6
7 8
7 9
输出
3
算法
Java 代码
import java.util.*;
import java.io.*;
public class Main{
public static void main(String[] args) throws IOException{
BufferedReader reader=new BufferedReader(new InputStreamReader(System.in));
int n=Integer.valueOf(reader.readLine());
int[][] arr=new int[n][2];
int k=0;
while(k<n){
String[] s=reader.readLine().split(" ");
arr[k][0]=Integer.valueOf(s[0]);
arr[k][1]=Integer.valueOf(s[1]);
k++;
}
Arrays.sort(arr,(a,b)->a[0]-b[0]);
int res=1;
int start=arr[1][0],end=arr[1][1];
for(int i=1;i<arr.length;i++){
//需要合并区间的只有两种情况,
//1.___ 2._____
// ____ __
if(arr[i][0]<=end){
end=Math.max(end,arr[i][1]);
}else{
res++;
start=arr[i][0];
end=arr[i][1];
}
}
System.out.print(res);
}
}
我是傻逼