题目描述
给定 n 个区间 [li,ri],要求合并所有有交集的区间。
注意如果在端点处相交,也算有交集。
输出合并完成后的区间个数。
例如:[1,3]和[2,6]可以合并为一个区间[1,6]。
输入格式
第一行包含整数n。
接下来n行,每行包含两个整数 l 和 r。
输出格式
共一行,包含一个整数,表示合并区间完成后的区间个数。
数据范围
1≤n≤100000,
−109≤li≤ri≤109
样例
5
1 2
2 4
5 6
7 8
7 9
java模板
// 将所有存在交集的区间合并
int l = Integer.MIN_VALUE;
int r = Integer.MIN_VALUE;
for(int[] a : list)
{
if(a[0] > r){
if(l != Integer.MIN_VALUE){
res.add(new int[]{l,r});
}
l = a[0];
r = a[1];
}else{
r = Math.max(r,a[1]);
}
}
if(l != Integer.MIN_VALUE) res.add(new int[]{l,r});
System.out.print(res.size());
}
Java代码
import java.util.Scanner;
import java.util.List;
import java.util.ArrayList;
import java.util.Comparator;
public class Main{
public static void main(String[] args){
Scanner in = new Scanner(System.in);
int n = in.nextInt();
List<int[]> list = new ArrayList<>();
for(int i = 0; i < n; i ++)
{
int l = in.nextInt();
int r = in.nextInt();
list.add(new int[]{l,r});
}
list.sort(new Comparator<int[]>(){ //按照左端点的大小进行排序
@Override
public int compare(int[] a1, int[] a2){
return a1[0] - a2[0];
}
});
List<int[]> res = new ArrayList<>();
int l = Integer.MIN_VALUE;
int r = Integer.MIN_VALUE;
for(int[] a : list)
{
if(a[0] > r) //当前区间的左端点大于上一个区间的右端点
{ // 第三种情况,找到一个新的区间,把上一个区间放到res中
if(l != Integer.MIN_VALUE){
res.add(new int[]{l,r});
}
l = a[0]; //把维护的区间 更新到 新的区间
r = a[1];
}
else //第一二种情况,比较r的大小
{
r = Math.max(r,a[1]);
}
}
if(l != Integer.MIN_VALUE) res.add(new int[]{l,r});
System.out.print(res.size());
}
}
解析
1:算法思想
- 1:把数组按照左端点从小到大的顺序排序
-
2:维护一个区间,和下一个区间进行对比,会分为三种情况
-
第一种:当前的区间完全被上一个区间所覆盖,这个时候我们就不用管,直接跳过就可以了
- 第二种:当前的区间比上一个区间的长度长,这个时候我们就更新右端点为长的内一个
- 第三种:当前的区间左端点大于上一个区间的右端点;此时的话,我们维护的区间要从上一个更新到当前的区间,因为上一个区间的长度已经达到最长了,
![![H)O$9OS(0NV4@4NQ%06[WM1.png](https://cdn.acwing.com/media/article/image/2021/01/01/60192_bfab5f8e4c-H)O$9OS(0NV4@4NQ%06[WM1.png) ]
2:如何按照左端点从左到右排序
Java的话会比c++代码麻烦一些,这里是传递了一个自定义的比较器Comparator,然后重写下面的compare方法
这个方法有三种返回值
第一个参数在前面,第二个参数在后面 第一个参数>第二个参数
1:正数;表示左值大于右值,会从小到大排序
2:=0;说明当前的两个值相同,会比较下面的值
3:负数;表示左值小于右值,会从大到小排序
如果写成a - b,那么在比较的过程有正有负,会通过不断的插入,更换位置,变成有序的
list.sort(new Comparator<int[]>(){ //按照左端点的大小进行排序
@Override
public int compare(int[] a1, int[] a2){
return a1[0] - a2[0];
}
});
3:为什么l,r并没有像y总一样设置成-2e9呢
因为在java里-2e9是浮点类型的,我们的边界l,r是整数类型的,浮点类型向整数类型转化会出现转化异常,就需要强制类型转化,也可以设置成Integer.MIN_VALUE,作用是一样的
//这样也是可以的
int l = (int)-2e9;
int r = (int)-2e9;
4:为什么把r设置成Integer.MIN_VALUE,而不是Integer.MAX_VALUE;
这是容易让我们维护第一个传进来的区间[1,2],如果是Integer.MAX_VALUE的话,在比较的时候,a[0] 肯定是小于 r的,我们就无法更新 新区间
5:为什么要加上if(l != Integer.MIN_VALUE) 这个判断
如果不加上这个判断的话,就会把[Integer.MIN_VALUE,Integer.MIN_VALUE]这个区间也加入到res数组中,大家也可以去掉试验一下
6:把区间加入到res数组中的两种方式
-
1:当前区间的左端点大于上一个区间的右端点,我们就需要维护一个新的区间,然后上一个区间就可以res数组中去了,因为此时上一个区间的长度不能在长了,排完序后是一个有序的数组,后面的区间只会比上一个区间大;
-
2:当合并最后一个区间后,因为已经没有新的区间把当前区间顶到res数组中去,所以我们需要单独写一段代码,把最后一个区间加入到res数组中去
7:模板分析
int l = Integer.MIN_VALUE;
int r = Integer.MIN_VALUE;
for(int[] a : list)
{
if(a[0] > r){
if(l != Integer.MIN_VALUE){
res.add(new int[]{l,r});
}
l = a[0];
r = a[1];
}else{
r = Math.max(r,a[1]);
}
}
if(l != Integer.MIN_VALUE) res.add(new int[]{l,r});
System.out.print(res.size());
}
1:首先经过前面的输入处理,list应该是[1,2],[2,4],[5,6],[7,8],[7,9],然后一个一个传递给int[] t
2:if(a[0] > r) 的意思是如果当前区间的左端点大于上一个区间的右端点,那就是我们说的第三种情况,就可以把上一个区间加入到res数组中,然后更新维护的区间;
3:else否则的话,就会出现第一二种情况,我们只需要把右端点更新到最长就可以了
4:if(l != Integer.MIN_VALUE) res.add(new int[]{l,r});
当合并最后一个区间后,因为已经没有新的区间把当前区间顶到res数组中去,所以我们需要单独写一段代码,把最后一个区间加入到res数组中去