算法解析
这道题的思路很好想,可以明显看出来可以用区间合并做,只要你学过区间合并,就肯定能想起来
温馨提示:区间合并是在算法基础课的第一章的最后一道题中
扩展题:区间合并
算法思想
1:把数组按照左端点从小到大的顺序排序
2:维护一个区间,和下一个区间进行对比,会分为三种情况
- 第一种:当前的区间完全被上一个区间所覆盖,这个时候我们就不用管,直接跳过就可以了
- 第二种:当前的区间比上一个区间的长度长,这个时候我们就更新右端点为长的内一个
- 第三种:当前的区间左端点大于上一个区间的右端点;此时的话,我们维护的区间要从上一个更新到当前的区间,因为上一个区间的长度已经达到最长了
代码
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 L = in.nextInt();
int m = in.nextInt();
List<int[]> list = new ArrayList<>(); //初始化
for(int i = 0; i < m; 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[] a, int[] b){
return a[0] - b[0];
}
});
List<int[]> arr = new ArrayList<>();
int l = Integer.MIN_VALUE;
int r = Integer.MIN_VALUE;
for(int[] a : list) //分为三种情况
{
if(a[0] > r){ //第三种情况,有了新区间以后,把旧区间顶到arr中去
if(l != Integer.MIN_VALUE) arr.add(new int[]{l,r});
l = a[0];
r = a[1];
}else{
r = Math.max(r,a[1]); //第一二种情况,比较右区间的大小,取最大就行
}
}
if(l != Integer.MIN_VALUE) arr.add(new int[]{l,r}); //把最后一个区间单独加到新数组中去,因为已经没有新区间可顶了
int res = 0;
for(int[] p : arr){
res += (p[1] - p[0] + 1); //每个区间的长度是l - r + 1
}
System.out.print(L + 1 - res); //因为是从0~500,所以有500+1个数
}
}
我想问一下区间合并的时间复杂度为什么是O(nlogn)
list.sort()里面用的是归并排序 + 二分优化,归并排序时间复杂度是O(nlogn),也就是排序的时间复杂度是O(nlogn),然后后面分三种情况只遍历了一遍,所以时间复杂度是O(n);O(nlogn) + O(n)=>O(nlogn)
十分谢谢
因为涉及到了List的源码,所以最好记住排序的时间复杂度是O(nlogn)就可以了
好滴
优秀
没学过,借鉴一下